The Idiot of the Year Contest!

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.

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$).

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