Alice and Bob start playing a new game. Alice writes 2 numbers - N and K. She asks Bob to find an integer which is N digits long such that the absolute difference in the adjacent digits is greater than or equal to K. Bob realizes that a lot of integers satisfy this condition.  Can you help Bob to find the total number of N digit integers which satisfy the condition set by Alice?
Since the answer can be very large, print the answer modulus 1000000007.

Note :

The adjacent digits to a digit constitute both the left and right neighbor of the digit. Starting from the left, only the second digit is regarded as adjacent to the first digit and only the second last digit is regarded as adjacent to the last digit.

Constraints

T = 100
2 <= N <= 10^9
0 <= K <= 9

Input

First line contains T- the number of test cases. The next T lines contains two numbers N and K as given by Alice.

Output

Print T lines each containing the total number of integers of N digit mod 1000000007 which satisfy the condition set by Alice.

Example

Input:
2
2 9
2 8
 
Output:
1
4