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 separated 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

Input:
4
1 1
2 1
2 2
3 3

Output:
45
4500
2475
136125

Explanation

For test 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.