소수의 주기

계산기 없이 두 수의 나눗셈을 손으로 계산하는 연습을 하려고 한다. 이번 시험에는 $b$진법으로 나타낸 두 수를 나눴을 때 그 몫의 주기의 길이를 구하는 문제가 나온다. 손으로 계산한 결과가 맞는지 확인해 주는 프로그램을 작성하자.

진법 $b$, 분자 $x$, 분모 $y$가 주어진다. $x$와 $y$는 모두 $b$진법으로 나타낸 수이다. $b$진법 수 $q = \dfrac{x}{y}$의 순환마디(주기)의 길이를 구하는 프로그램을 작성하시오. 유리수 $q$를 $b$진법으로 나타내는 방법은 다음과 같다.

$q = q_n q_{n-1} \dots q_0 . q_{-1} q_{-2} \dots = \sum_{i=-\infty}^{n} q_i b^i$

예를 들어 보자.

• $\dfrac{1_{10}}{2_{10}} = 0.5_{10}$
• $\dfrac{1_{3}}{10_{3}} = 0.1_{3}$
• $\dfrac{2_{10}}{11_{10}} = 0.181818\dots_{10} = 0.\overline{18}_{10}$

위의 처음 두 예는 유한소수이므로 주기의 길이는 $0$이다. 첫 번째 예를 주기의 길이가 $1$인 $0.4\overline{9}_{10}$으로 나타낼 수도 있지만, 이 문제에서는 그런 표현은 고려하지 않는다. 세 번째 예의 주기의 길이는 $2$이다.

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 진법 $b$, 분자 $x$, 분모 $y$가 공백으로 구분되어 주어진다. ($2 \le b \le 36$, $0 < y \le 10000010$)

$b$는 10진법으로 주어지고, $x$와 $y$는 $b$진법으로 주어진다. $0$부터 $9$까지의 숫자로 나타낼 수 없는 자리는 a(또는 A)부터 시작하는 알파벳으로 나타내며, 대소문자는 구별하지 않는다.

각 테스트 케이스마다 Scenario #i:를 출력한 뒤, 다음 줄에 주기의 길이를 출력한다. ($i$는 테스트 케이스 번호로 $1$부터 시작한다.) 각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.