Froggy loves numbers and rainbows. Today, he wants to combine these two of his favorite things. He defines rainbow numbers are numbers satisfying the following constraints.
• The number is a non-negative integer.
• The decimal representation of the number can be written as a1a2 · · · an where ai ∈ {0, 1, . . . , 9} for i ∈ {1, 2, . . . , n}.
• There is no leading zeros. That is, a1 ̸= 0 if n > 1.
• Any two consecutive digits of the number must different. That is, for 1 < i ≤ n, ai−1 ̸= ai . For instances, 1213 and 384379 are rainbow numbers. Note that 2334 is not a rainbow number, because there are consecutive 3’s. Just like rainbows, two consecutive tracks are in different colors.
Given two integers L and R, please help Froggy find out how many rainbow numbers there are within the interval [L, R]
The first line contains an integer T indicating the number of testcases. Each test case is one line containing two integers L and R.
For each testcase, output how many rainbow numbers are in the interval [L, R]. If there are more than 1000000006, then output the answer modulo 1000000007. Technical Specification
• 1 ≤ T ≤ 20
• 0 ≤ L ≤ R < 10^100
Sample Input 1 1 5 20 Sample Input 2 2 330 339 330 340
Sample Output 1 15 Sample Output 2 0 1
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||