You are given a number N. You can perform the following operation on it:-
Change any digit of N to a different digit. The cost of this operation is the absolute difference between the original and changed digits.
This operation can be performed any number of times. For example let N=12 , if we change the first digit to 2 and second digit to 1 the result becomes 21. The total cost involved in the conversion is |1-2| + |2-1|=2.
Your task is to determine how many distinct numbers which are divisible by 3 can be generated in this manner from the number N so that total cost of each conversion is less than equal to a given number C. You cannot change the first digit to 0.Here first digit implies the left most digit of an integer.

Input Format

The first line would consist of the number of test cases 'T'. This would be followed by 'T' lines consisting of two space separated integers N and C.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 10^50
1 ≤ C ≤ 2000

Output Format

For each test case output a single integer denoting the required value. Since the answer can be very large output the required value modulo 10^9+7.

Explanation For Sample Test

For the first case there are 8 such possible numbers:- 12,15,21,24,30,33,42 and 51.

SAMPLE INPUT
2
12 5
234 3

SAMPLE OUTPUT
8
24

见题面

见题面