Elon Musk’s Crazy Contraption

Problem Statement:

In the time that Elon Musk isn’t driving the price of obscure cryptocurrencies to the moon, he thinks of ideas for crazy contraptions. This week he built a machine which takes a number and does the following operations in order:

1. Multiplies the number by 13
2. Multiplies the number by 11
3. Multiplies the number by 7
4. Outputs all the distinct 3-digit numbers possible from the result of the above operations (such that each digit can only be used once).

Elon, to test his machine, does the following N times:

1. Given a 3-digit positive number K, he feeds it to the contraption for processing.
2. He then takes the numbers it gives as output, and sends it through the contraption again

Help Elon find the number of distinct 3-digit numbers which the device outputs over the N steps.

Constraints:

• Each digit of K is non-zero

Subtask 1: 20 points

• 1 ≤ T ≤ 1000

Subtask 2: 80 points

• 5 ≤ N ≤ 10⁹

Input Format:

• First line will contain T, number of testcases. Then the testcases follow.
• Each testcase contains of a single line of input, two integers K, N

Output Format:

• For each test case, print the number of distinct 3-digit numbers which the device outputs over the N steps.

Sample input:

1 123 5 

Sample output:

27