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