Number Tricks

Dora loves impressing her friends with number tricks. One of her favorite tricks is to have a friend name a number $n$; Dora then tells them how many zeroes appear at the end of $n!$. Her friends are usually very impressed, because $n!$ is such a large number. For example, when $n = 100$, even though $n!$ is larger than the estimated number of atoms in the universe, Dora can instantly say that $n!$ ends in exactly $24$ zeroes.

Some of Dora's newest friends, however, are aliens with more or fewer than ten fingers. Like every life form she has met so far, they count in a number system that has as many digits as they have fingers. Dora wants to impress them too, but she is not sure how to adapt her trick. Can you help her?

Given a base $b$ and a number $n$, compute how many zeroes appear at the end of $n!$ when it is written in base $b$. For example, take $b = 2$ and $n = 5$. Since $5! = 120 = 1111000_2$, the answer is $3$.

The first line contains the number of scenarios. Each of the following lines describes one scenario and contains two integers $b$ and $n$ ($2 \le b \le 1000$, $1 \le n \le 1\,000\,000$), both given in base ten.

For each scenario, first print a line Scenario #i:, where $i$ is the scenario number starting at $1$. Then print a single line containing $k$ (in base ten), the number of trailing zeroes of $n!$ when it is written in base $b$. Separate consecutive scenarios with a blank line.