시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 50.000%

문제

선영이는 계산기가 없으면 두 수의 나눗셈을 계산할 수 없다. 선영이는 다가오는 시험을 대비하기 위해 나눗셈을 계산해보려고 한다. 이번 시험에는 \(b\)진법으로 나타낸 두 수를 나눴을 때, 주기의 길이를 구하는 문제가 나온다. 선영이는 자신이 손으로 계산한 결과가 정답과 맞는지를 확인하는 프로그램을 작성하려고 한다.

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

\(q=q_{n}q_{n-1}\dots q_{0}.q_{-1}q_{-2} \dots = \sum _{i=-\infty } ^{n}{q_ib^i}\)

아래는 예이다.

\(\frac {1_{10}}{2_{10}} = 0.5_{10}\), \(\frac {1_3} {10_3} = 0.1_3\), \(\frac {2_{10}}{11_{10}} = 0.181818\dots_{10} = 0.\overline { 18 }  _{10}\)

위의 처음 두 예제는 유한 소수이다. 따라서, 주기의 길이는 0이다. 첫 번째 예제의 경우에 주기의 길이가 1인 \(0.4\overline { 9 } _{ 10 }\)로 나타낼 수 있지만, 이 문제에서 그러한 경우는 신경쓰지 않는다.

세 번째 예제의 경우 주기의 길이는 2이다. 

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, \(b\), \(x\), \(y\)가 주어진다. (2 ≤ \(b\) ≤ 36, 0 < \(y\) ≤ 10000010) 0부터 9까지 숫자로 나타낼 수 없는 자리는 'a'와 'A'로 시작하는 글자로 나타낸다. 이때, 대소문자는 구별하지 않는다. 

출력

각 테스트 케이스마다 "Scenario #i:"를 출력한 다음에, 주기의 길이를 출력한다. 각 테스트 케이스 사이에는 빈 칸을 하나 출력한다.

예제 입력 1

4
10 1 2
3 1 10
10 2 11
36 HI ho

예제 출력 1

Scenario #1:
0

Scenario #2:
0

Scenario #3:
2

Scenario #4:
13
W3sicHJvYmxlbV9pZCI6Ijc1NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMThcdWM3NTggXHVjOGZjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVhY2M0XHVjMGIwXHVhZTMwXHVhYzAwIFx1YzVjNlx1YzczY1x1YmE3NCBcdWI0NTAgXHVjMjE4XHVjNzU4IFx1YjA5OFx1YjIxN1x1YzE0OFx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjJlNFx1YWMwMFx1YzYyNFx1YjI5NCBcdWMyZGNcdWQ1ZDhcdWM3NDQgXHViMzAwXHViZTQ0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIwOThcdWIyMTdcdWMxNDhcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTc0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViYzg4IFx1YzJkY1x1ZDVkOFx1YzVkMFx1YjI5NCBcXChiXFwpXHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWI0NTAgXHVjMjE4XHViOTdjIFx1YjA5OFx1YjIzNFx1Yzc0NCBcdWI1NGMsIFx1YzhmY1x1YWUzMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1YWMwMCBcdWIwOThcdWM2MjhcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjMTkwXHVjNzNjXHViODVjIFx1YWNjNFx1YzBiMFx1ZDU1YyBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjODE1XHViMmY1XHVhY2ZjIFx1YjlkZVx1YjI5NFx1YzljMFx1Yjk3YyBcdWQ2NTVcdWM3NzhcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljNFx1YmM5NSBcXChiXFwpLCBcdWJkODRcdWM3OTAgXFwoeFxcKSwgXHViZDg0XHViYWE4IFxcKHlcXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcXCh4XFwpXHVjNjQwIFxcKHlcXClcdWIyOTQgXHViYWE4XHViNDUwIFxcKGJcXClcdWM5YzRcdWJjOTVcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXFwoYlxcKVx1YzljNFx1YmM5NSBcdWMyMTggXFwocSA9IFxcZnJhYyB7eH0ge3l9XFwpXHVjNzU4IFx1YzhmY1x1YWUzMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNzIwXHViOWFjXHVjMjE4IFxcKHFcXClcdWI5N2MgYlx1YzljNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxcKHE9cV97bn1xX3tuLTF9XFxkb3RzIHFfezB9LnFfey0xfXFfey0yfSBcXGRvdHMgPSBcXHN1bSBfe2k9LVxcaW5mdHkgfSBee259e3FfaWJeaX1cXCk8XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4XHViMjk0IFx1YzYwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwoXFxmcmFjIHsxX3sxMH19ezJfezEwfX0gPSAwLjVfezEwfVxcKSwgXFwoXFxmcmFjIHsxXzN9IHsxMF8zfSA9IDAuMV8zXFwpLCBcXChcXGZyYWMgezJfezEwfX17MTFfezEwfX0gPSAwLjE4MTgxOFxcZG90c197MTB9ID0gMC5cXG92ZXJsaW5lIHsgMTggfSAmbmJzcDtfezEwfVxcKTxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVjYzk4XHVjNzRjIFx1YjQ1MCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjNzIwXHVkNTVjIFx1YzE4Y1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4ZmNcdWFlMzBcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDBcdWM3NzRcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM4ZmNcdWFlMzBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIDFcdWM3NzggXFwoMC40XFxvdmVybGluZSB7IDkgfSBfeyAxMCB9XFwpXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHVjOWMwXHViOWNjLCBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjMmUwXHVhY2JkXHVjNGYwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwIFx1YzhmY1x1YWUzMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMlx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFxcKGJcXCksIFxcKHhcXCksIFxcKHlcXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IFxcKGJcXCkgJmxlOyAzNiwgMCAmbHQ7IFxcKHlcXCkgJmxlOyAxMDAwMDA8c3ViPjEwPFwvc3ViPikgMFx1YmQ4MFx1ZDEzMCA5XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWM3OTBcdWI5YWNcdWIyOTQgJiMzOTthJiMzOTtcdWM2NDAgJiMzOTtBJiMzOTtcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YWUwMFx1Yzc5MFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwXHViMjk0IFx1YWQ2Y1x1YmNjNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgJnF1b3Q7U2NlbmFyaW8gI2k6JnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWIyZTRcdWM3NGNcdWM1ZDAsIFx1YzhmY1x1YWUzMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzU0NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkV4dHJhIFRlcnJlc3RyaWFsIFBJU0EgVGVzdCIsImRlc2NyaXB0aW9uIjoiPHA+T24gdGhlIHBsYW5ldCBEaXZpZG8gdGVhY2hlcnMgaGF2ZSBhIHNlcmlvdXMgcHJvYmxlbS4gRHVlIHRvIHRoZSBzcHJlYWQgb2YgY2FsY3VsYXRvcnMgdGhlIHN0dWRlbnRzIGNhbm5vdCBkbyBsb25nIGRpdmlzaW9uIHdpdGggcGVuY2lsIGFuZCBwYXBlciBhbnkgbG9uZ2VyLiBCdXQgbm93IHRoZSBwbGFuZXRhcmlhbiBnb3Zlcm5tZW50IGhhcyBhbm5vdW5jZWQgYSB0ZXN0IGZvciBhbGwgc3R1ZGVudHMgaW4gYmFzaWMgc2Nob29scyB0byB0ZXN0IHRoZWlyIG1hdGggc2tpbGxzLiBCZWNhdXNlIGl0IGhhcyB0byBiZSBhIG11bHRpcGxlIGNob2ljZSB0ZXN0IHRoZSBzdHVkZW50cyBvbmx5IGhhdmUgdG8gY2FsY3VsYXRlIHRoZSBsZW5ndGggb2YgdGhlIHBlcmlvZCB3aGVuIGRpdmlkaW5nIHR3byBudW1iZXJzLiBZb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoIGNhbGN1bGF0ZXMgdGhlIHJpZ2h0IHNvbHV0aW9ucyBpbiBhZHZhbmNlIHRvIGVhc2UgdGhlIGNvcnJlY3Rpb24gb2YgdGhlIHRlc3QuIEFuIGFkZGl0aW9uYWwgcHJvYmxlbSBvY2N1cnMgYmVjYXVzZSBub3QgYWxsIGludGVsbGlnZW50IHNwZWNpZXMgb24gRGl2aWRvIGhhdmUgdGhlIHNhbWUgbnVtYmVyIG9mIFx1ZmIwMW5nZXJzIGFuZCB0aHVzIHRoZWlyIHN5c3RlbXMgb2YgbnVtYmVycyBoYXZlIGRpZmZlcmVudCBiYXNlcy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBhIGJhc2UgXFwoYlxcKSwgYSBudW1lcmF0b3IgXFwoeFxcKSwgYW5kIGEgZGVub21pbmF0b3IgXFwoeVxcKSwgdGhlIGxhdHRlciBvZiB3aGljaCBhcmUgaW50ZWdlcnMgdG8gdGhlIGJhc2UgXFwoYlxcKS4gVGhlbiBjYWxjdWxhdGUgdGhlIGxlbmd0aCBvZiB0aGUgcGVyaW9kIGluIHRoZSBiYXNlIFxcKGJcXCkgZXhwYW5zaW9uIG9mIHRoZSBmcmFjdGlvbiBcXChxID0gXFxmcmFje3h9e3l9XFwpLiBSZW1lbWJlciB0aGF0IHRoZSBkaWdpdHMgb2YgdGhlIGJhc2UgXFwoYlxcKSBleHBhbnNpb24gb2YgdGhlIHRoZSByYXRpb25hbCBudW1iZXIgXFwocVxcKSBhcmUgdGhlIGNvZWZcdWZiMDFjaWVudHMgb2YgdGhlIHBvd2VycyBvZiB0aGUgYmFzZTo8XC9wPlxyXG5cclxuPHA+XFwocT1xX3tufXFfe24tMX1cXGRvdHMgcV97MH0ucV97LTF9cV97LTJ9IFxcZG90cyA9IFxcc3VtIF97aT0tXFxpbmZ0eSB9IF57bn17cV9pYl5pfVxcKTxcL3A+XHJcblxyXG48cD5IZXJlIGFyZSBzb21lIGV4YW1wbGVzOjxcL3A+XHJcblxyXG48cD5cXChcXGZyYWMgezFfezEwfX17Ml97MTB9fSA9IDAuNV97MTB9XFwpLCBcXChcXGZyYWMgezFfM30gezEwXzN9ID0gMC4xXzNcXCksIFxcKFxcZnJhYyB7Ml97MTB9fXsxMV97MTB9fSA9IDAuMTgxODE4XFxkb3RzX3sxMH0gPSAwLlxcb3ZlcmxpbmUgeyAxOCB9ICZuYnNwO197MTB9XFwpPFwvcD5cclxuXHJcbjxwPkluIHRoZSBcdWZiMDFyc3QgdHdvIGV4YW1wbGVzLCB0aGVyZSBpcyBhIFx1ZmIwMW5pdGUgYmFzZSBcXChiXFwpIGV4cGFuc2lvbiBvZiB0aGUgZnJhY3Rpb24sIG1lYW5pbmcgdGhhdCBhbGwgZGlnaXRzIHRoYXQgZm9sbG93IGFyZSB6ZXJvLiBJbiB0aGF0IGNhc2UsIHdlIHNheSB0aGF0IHRoZSBsZW5ndGggb2YgdGhlIHBlcmlvZCBpcyB6ZXJvLiBOb3RlIHRoYXQgb25lIGNvdWxkIGFzIHdlbGwgZXhwcmVzcyB0aGUgXHVmYjAxcnN0IGV4YW1wbGUgYXMgXFwoMC40XFxvdmVybGluZSB7IDkgfSBfeyAxMCB9XFwpIHdpdGggYSBwZXJpb2QgbGVuZ3RoIG9mIG9uZSwgYnV0IHRoYXQgaXMgbm90IHdoYXQgd2Ugd2FudC48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHRoaXJkIGV4YW1wbGUsIGhvd2V2ZXIsIHRoZSBwZXJpb2QgbGVuZ3RoIGlzIHVuYW1iaWd1b3VzbHkgdHdvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgZnJhY3Rpb25zLiBGb3IgZWFjaCBmcmFjdGlvbiB5b3UgYXJlIFx1ZmIwMXJzdCBnaXZlbiB0aGUgYmFzZSBcXChiXFwpIGFzIGEgZGVjaW1hbCBudW1iZXIgd2l0aCAyICZsZTsgXFwoYlxcKSAmbGU7IDM2LCBhbmQgdGhlbiB0aGUgbnVtZXJhdG9yIFxcKHhcXCkgYW5kIHRoZSBkZW5vbWluYXRvciBcXCh5XFwpIG9mIHRoZSBmcmFjdGlvbiB0byB0aGF0IGJhc2Ugc2VwYXJhdGVkIGJ5IHNpbmdsZSBibGFua3MuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgZGVub21pbmF0b3Igc2F0aXNcdWZiMDFlcyAwICZsdDsgXFwoeVxcKSAmbGU7IDEwMCAwMDA8c3ViPjEwPFwvc3ViPi4gRGlnaXRzIG5vdCBpbiB0aGUgcmFuZ2Ugb2YgMC4uLjkgYXJlIHJlcHJlc2VudGVkIGJ5IGxldHRlcnMgc3RhcnRpbmcgZnJvbSAmbGRxdW87YSZyZHF1bzsgb3IgJmxkcXVvO0EmcmRxdW87IGluIHRoZSB1c3VhbCB3YXksIHdoZXJlIGNhc2UgZG9lcyBub3QgbWF0dGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgZm9yIGV2ZXJ5IHNjZW5hcmlvIGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nICZsZHF1bztTY2VuYXJpbyAjaTomcmRxdW87LCB3aGVyZSBpIGlzIHRoZSBudW1iZXIgb2YgdGhlIHNjZW5hcmlvIHN0YXJ0aW5nIGF0IDEuIFRoZW4gcHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBsZW5ndGggb2YgdGhlIHBlcmlvZCBpbiB0aGUgYmFzZSBcXChiXFwpIGV4cGFuc2lvbiBvZiBcXChcXGZyYWN7eH17eX1cXCkgLCBidXQgbWFrZSBzdXJlIHRvIHByaW50IHRoZSBsZW5ndGggYXMgYSBkZWNpbWFsIG51bWJlci4gVGVybWluYXRlIHRoZSBvdXRwdXQgZm9yIHRoZSBzY2VuYXJpbyB3aXRoIGEgYmxhbmsgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==