A digit of a decimal integer N is a local maximum if it is bigger than both of its adjacent digits. For simplicity, the first and last digits of a number are not local maximum.
Let us consider a signature of a decimal number N which is defined as the number of local maximum digits of that number. Your task is to write a program to compute the sum of signatures of all numbers in a range from X to Y inclusively.
The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 50000. The following lines describe the data sets.
Each data set consists of only one line, which contains two integers X and Y separated by a space (0 ≤ X ≤ Y ≤ 1015).
For each data set, write in one line the sum for the signatures of all numbers in the range from X to Y inclusively.
4 1 100 121 121 909 909 100 150
0 1 0 10
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi
| No. | Testdata Range | Score |
|---|