강의의 함정

학생을 가르치는 일은 즐겁지만 가끔은 창피한 순간이 온다. 며칠 전 내가 겪은 일이다. 대학 강의 첫 시간이라 아주 기본적인 내용을 다루고 있었는데, $b$진법으로 적은 $n!$의 끝에 0이 몇 개 붙는지 구하는 방법이었다. 소수 $p$가 $n!$을 나누는 횟수는 다음 식으로 구한다.

$\left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots$

이 식을 잘 쓰면 $n!$의 끝에 붙는 0의 개수도 구할 수 있다.

식을 설명한 뒤 10진법에서 $200!$의 끝에 붙는 0의 개수를 함께 구했고, 짓궂은 표정으로 16진법에서 $100!$의 끝에 0이 몇 개 붙는지 물었다. 답이 24라는 것은 이미 알고 있었다. 그런데 몇 분 만에 한 학생이 24라고 정답을 말해서 놀랐고, 나는 그를 칭찬했다. 잠시 뒤 그 학생의 계산을 확인해 보니 16진법이 아니라 10진법에서 $100!$의 끝에 붙는 0을 센 것이었다. 두 값이 우연히 모두 24였을 뿐이다. 조금 민망해진 나는 왜 두 값이 같았는지 알고 싶다.

2 이상의 정수 $b$에 대해, $n!$을 $b$진법으로 적었을 때 마지막 자리부터 연속으로 이어지는 0의 개수를 $Z(n, b)$라고 하자. $n$과 $x$가 주어질 때, $2 \le b_1 < b_2$이고 어떤 정수 $p \ge x$에 대해 $Z(n, b_1) = Z(n, b_2) = p$인 쌍 $(b_1, b_2)$의 개수를 구하라.

입력은 여러 줄로 이루어진다. 각 줄에는 정수 $n$ ($1 \le n \le 100000$)과 $x$ ($2 \le x \le 2500$)가 공백으로 구분되어 주어진다. 마지막 줄에는 0이 두 개 주어지며, 이 줄은 처리하지 않는다. 마지막 줄을 빼면 입력의 줄 수는 1000개를 넘지 않는다.

입력의 각 줄마다 쌍 $(b_1, b_2)$의 개수를 한 줄에 출력한다. 어떤 출력값도 $5 \times 10^{18}$을 넘지 않는 입력만 주어진다.