숫자 마술
면접 대비시간 제한1초메모리 제한128 MB
각 질의에서 b를 소인수분해한 뒤, n!에 포함된 각 소인수의 지수를 세어 최솟값으로 b진법 n!의 끝자리 0 개수를 구한다.
문제
도라는 숫자 마술로 친구들을 놀라게 하는 것을 좋아한다. 그녀가 즐겨 쓰는 마술 중 하나는, 친구에게 어떤 수 을 말하게 한 뒤 의 끝에 이 몇 개 붙는지 곧바로 알려 주는 것이다. 은 아주 큰 수이기 때문에 친구들은 대개 크게 감탄한다. 예를 들어 이면 은 우주에 있는 원자 수의 추정치보다도 크지만, 도라는 이 정확히 개의 으로 끝난다는 것을 즉시 말할 수 있다.
그런데 도라의 새 친구들 중에는 손가락이 열 개보다 많거나 적은 외계인도 있다. 지금까지 만난 모든 생명체처럼, 그들도 손가락 수만큼의 숫자를 가진 수 체계로 수를 센다. 도라는 그들도 놀라게 하고 싶지만, 마술을 어떻게 바꿔야 할지 확신이 서지 않는다. 그녀를 도와줄 수 있겠는가?
밑 와 수 이 주어질 때, 을 진법으로 나타냈을 때 끝에 붙는 의 개수를 구하라. 예를 들어 , 라고 하자. 이므로 답은 이다.
입력
첫째 줄에는 시나리오의 개수가 주어진다. 이어지는 각 줄은 하나의 시나리오를 나타내며, 두 정수 와 이 주어진다 (, ). 두 수 모두 십진법으로 주어진다.
출력
각 시나리오마다 먼저 Scenario #i: 줄을 출력한다. 여기서 는 부터 시작하는 시나리오 번호이다. 그다음 줄에는 을 진법으로 나타냈을 때 끝에 붙는 의 개수 를 십진법으로 한 줄에 출력한다. 연속한 시나리오 사이는 빈 줄로 구분한다.