Now that Chhaya (Mahima's sister) has found the deterministic probability of winning (losing?) strategy for game of dice with your help, her brother Satyam, comes up with a new game as a substitute. The game works as follows..
Satyam will give 2 numbers - R and P to Chhaya. He asks Chhaya who is very intelligent to find an integer which is R digits long (with no leading zeroes) and in which the absolute difference in the adjacent digits is less than or equal to P.
Satyam considers such numbers to be Majestic Numbers. Chhaya realizes that a lot of integers satisfy this condition. Can you help Chhaya to find the total number of Majestic Numbers
Since the answer can be very large, print the answer modulus 109+7.
Input:
First line of input contains a positive integer T - no. of test cases
Next T lines have two integers representing R and P.
Output:
Print an integer containing the answer on T separate lines for each test case.
Constraints:
1 ≤ T ≤102
2 ≤ R ≤ 6
0 ≤ P ≤ 9
Problem Setter: MAHIMA SINGH
Explanation:-
Only 1 test case is provided with R=2 and P=1
There can be 26 numbers which are 2 digits long and in which the absolute difference in the adjacent digits is less than or equal to 1. The numbers are as follows:-
11, 22, 33, 44, 55, 66, 77, 88, 99, 10, 12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21
So, the output is 26.
