The Idiot of the Year Contest!

Time limit1sMemory limit128 MB

Summary

For each test case, count how many times a chosen digit occurs in the decimal representation of n! where n is at most 366.

Level: Medium4 of 10
Topics: Math, Implementation, Array, Simulation
Solved: No attempts yet

Problem

The Idiot of the Year Contest (IYC) has just one basic rule! Each contestant picks a single digit from $0$ to $9$ , computes the factorial of the number of the day of the year on which they were born, and counts how many times the chosen digit appears in that factorial. The contestant with the highest count becomes the Idiot of the Year!

For example, if someone was born on the $129$ th day of the year and picked the digit $6$ , their score is the number of times the digit $6$ appears in $129!$ (that is, $1 \times 2 \times 3 \times \dots \times 129$ ).

The chief judge wants you to write a program that reads the day of the year on which a contestant was born and the digit they picked, and reports how many times that digit appears in the factorial of the day number.

Input

The first line of the input contains a single integer $T$ , the number of test cases. Each of the following $T$ lines contains two numbers: the first is the day of the year on which a contestant was born, and the second is the digit they picked (from $0$ to $9$ ).

Output

Print $T$ lines. Each line contains a single integer: the number of times the chosen digit appears in the factorial of the first number.

Examples1

Example 1
Input
```
2
5 2
7 0
```
Expected output
```
1
2
```