The Idiot of the Year Contest!#5040
The Silly New Year Contest (SNYC) has only one rule! Each contestant picks any digit between and , calculates the factorial of the day of the year they were born on, and counts how many times the chosen digit appears in the factorial. The contestants who obtain the highest count are declared the Fools of the Year!
For example, if you were born on the th day of the year and chose the digit , your score would be the number of times the digit occurs in the decimal representation of (that is, 129! = 1 \times 2 \times 3 \times \ldots \times 129).
The chief judge of SNYC wants you to write a program which, given the day-of-the-year number and a digit for several contestants, reports how many times the digit occurs in the factorial of the given number.
The first line contains a single integer — the number of test cases. Each of the following lines contains two integers: the first is the contestant's day-of-the-year number, and the second is the digit they chose.
Output lines. For each test case, print a single integer — the number of times the chosen digit appears in the factorial of the day-of-the-year number.
Example 1