Finding Tricky Numbers

Albert learned about integers, digits, and subtraction at school. To amuse himself when bored, he invented a game called "tricky numbers."

To play, you first choose a digit A between 0 and 9. Then you must find the K-th smallest "A-tricky number," where a positive integer X is called an "A-tricky number" if it satisfies the following conditions.

• If X has one digit, it is an "A-tricky number."
• If X has two or more digits and no pair of adjacent digits in X has a difference less than A, it is an "A-tricky number."

For example, when A = 0, every positive integer is an "A-tricky number."

When A = 1, the first 30 "A-tricky numbers" are as follows.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, ...

Given A and K, write a program to find the K-th smallest "A-tricky number." Since the answer can be very large, print it modulo 10^9+7.

The first line gives the number of test cases T (1 ≤ T ≤ 100). The next T lines each give K and A. The two integers are separated by a space. (1 ≤ K ≤ 10^18, 0 ≤ A ≤ 9)

For each test case, print the K-th smallest "A-tricky number" modulo 10^9+7, one per line.