Fascinated as he is by the uncanny world of electronics, our friend MKS now decides to launch his own creation --> A N-Digit Carry Finder(an analogue of a N-Bit Binary Adder) which can be used to find the number of times we can have a non-zero carry while adding two numbers(A=A_nA_n-1...A₂A₁ and B=B_nB_n-1...B₂B₁) having exactly N digits.

It consists of 'N' Full Decimal Adders. The i-th Full Adder takes as input three digits A_i,B_i and C_i-1 and outputs a digit C_i(0 or 1), which is the carry generated on adding the digits A_i and B_i and C_i-1.(C_i=1 if A_i+B_i+C_i-1 >9, otherwise 0).

This C_i is now provided to the next (i+1-th) Full Adder in order to be added with the digits A_i+1 and B_i+1 and also to the accumulator which as the name suggests accumulates the sum of all C_j(1<=j<=i).

Note: C₀=0 always and 0<=A_i,B_i<=9.

For Example: Adding two numbers , A=4567 and B=734(or B=0734), the addition proceeds as shown and the accumulator gets a final value of 3.

In the 1st Adder, A₁=7,B₁=4,C₀=0 and A₁+B₁+C₀=11. Therefore Carry C₁=1.

In the 2nd Adder, A₂=6,B₂=3,C₁=1 and A₂+B₂+C₁=10. Therefore Carry C₂=1.

In the 3rd Adder, A₃=5,B₃=7,C₂=1 and A₃+B₃+C₂=13. Therefore Carry C₃=1.

In the 4th Adder, A₄=7,B₄=0,C₃=1 and A₄+B₄+C₃=8. Therefore Carry C₄=0.

The Value in the Accumulator=C₁+C₂+C₃+C₄=3.

Your Task is to find the number of ways of getting a value K in the accumulator while adding two numbers containing  at most N digits each. Note that we are adding the numbers in their base 10 representation. Since the total number of ways can be very large, print your answer modulo 1000000007(10^9 +7).

Input

The first line of input contains an integer T. Then T lines follow containing two space seperated integers N and K.

Output

Print the required answer modulo 1000000007(10^9 +7) in the i^th line corresponding to the i^th Test case .

Constraints:

1<=T<=500.

1<=N<=1000.

1<=K<=N.

Example

Sample Input

4

1 1

2 1

2 2

3 3

Sample Output

45

4500

2475

136125

Explanation

Example case 1.

The carry appears when adding 

1 and 9, 2 and 9, 3 and 9 ... 9 and 9=9 cases.

2 and 8,3 and 8,4 and 8 ... 9 and 8=8 cases.

3 and 7,4 and 7,5 and 7 ... 9 and 7=7 cases.

.

.

.

9 and 1=1 case.

There are (9+8+7+6+5+4+3+2+1+0)=45 cases in total and in each case, the carry appears exactly once.