숫자 마술

도라는 숫자 마술로 친구들을 놀라게 하는 것을 좋아한다. 그녀가 즐겨 쓰는 마술 중 하나는, 친구에게 어떤 수 $n$을 말하게 한 뒤 $n!$의 끝에 $0$이 몇 개 붙는지 곧바로 알려 주는 것이다. $n!$은 아주 큰 수이기 때문에 친구들은 대개 크게 감탄한다. 예를 들어 $n = 100$이면 $n!$은 우주에 있는 원자 수의 추정치보다도 크지만, 도라는 $n!$이 정확히 $24$개의 $0$으로 끝난다는 것을 즉시 말할 수 있다.

그런데 도라의 새 친구들 중에는 손가락이 열 개보다 많거나 적은 외계인도 있다. 지금까지 만난 모든 생명체처럼, 그들도 손가락 수만큼의 숫자를 가진 수 체계로 수를 센다. 도라는 그들도 놀라게 하고 싶지만, 마술을 어떻게 바꿔야 할지 확신이 서지 않는다. 그녀를 도와줄 수 있겠는가?

밑 $b$와 수 $n$이 주어질 때, $n!$을 $b$진법으로 나타냈을 때 끝에 붙는 $0$의 개수를 구하라. 예를 들어 $b = 2$, $n = 5$라고 하자. $5! = 120 = 1111000_2$이므로 답은 $3$이다.

첫째 줄에는 시나리오의 개수가 주어진다. 이어지는 각 줄은 하나의 시나리오를 나타내며, 두 정수 $b$와 $n$이 주어진다 ($2 \le b \le 1000$, $1 \le n \le 1\,000\,000$). 두 수 모두 십진법으로 주어진다.

각 시나리오마다 먼저 Scenario #i: 줄을 출력한다. 여기서 $i$는 $1$부터 시작하는 시나리오 번호이다. 그다음 줄에는 $n!$을 $b$진법으로 나타냈을 때 끝에 붙는 $0$의 개수 $k$를 십진법으로 한 줄에 출력한다. 연속한 시나리오 사이는 빈 줄로 구분한다.