Cat Taro recently discovered how to reverse a number. He defines a function rev(x) that returns the reverse of the base-10 representation of x without any leading zeros. For example, rev(13) = 31, rev(1420) = 241, rev(241) = 142, rev(0) = 0.
He also recently learned about multiples of k. A multiple of k can be written as k * x for some nonnegative integer x. He is interested in the number of multiples of k such that the number of digits is at most n and its reverse is also a multiple of k. However, he doesn't know how to compute this quantity, so he asks for your help. This number can get very large, so he would like this count modulo 1,000,000,007.
Input Format
The first line of the input will contain an integer T, denoting the number of test cases.
Each test case is a single line that contains 2 integers n, k.
Output Format
Print a single line per test case, the answer to Cat Taro's question.
Constraints
For all files
1 ≤ T ≤ 20
1 ≤ n
2 ≤ k ≤ 10
File 1 -- 22 pts:
n ≤ 3
File 2 -- 19 pts:
n ≤ 6
File 3 -- 17 pts:
n ≤ 100
File 4 -- 15 pts
n ≤ 1,000,000,000
k = 2 or 5
File 5 -- 15 pts
n ≤ 1,000,000,000
k = 3 or 9
File 6 -- 12 pts:
n ≤ 1,000,000,000
In the first sample case, we want to count the number of numbers with at most two digits such that both the number and its reverse are divisible by 3. As all reverses of multiples 3 are also multiples of 3s themselves, the number of at most 2 digit multiples of 3 is 34, which is the answer to this case (note that zero is included).
The second sample case wants us to count the number of numbers with at most 5 digits such that the number and its reverse is divisible by 7.
In the third sample case, the answer is modulo 1,000,000,007.
In the last sample case, zero is the only number whose reverse is also divisible by 10.
