시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVjMTM4XHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjAgXHVjOGZjXHVhZTMwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAyXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXFwoYlxcKSwgXFwoeFxcKSwgXFwoeVxcKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgXFwoYlxcKSAmbGU7IDM2LCAwICZsdDsgXFwoeVxcKSAmbGU7IDEwMDAwMDxzdWI+MTA8XC9zdWI+KSAwXHViZDgwXHVkMTMwIDlcdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNWM2XHViMjk0IFx1Yzc5MFx1YjlhY1x1YjI5NCAmIzM5O2EmIzM5O1x1YzY0MCAmIzM5O0EmIzM5O1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhZTAwXHVjNzkwXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwXHViMjk0IFx1YWQ2Y1x1YmNjNFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgJnF1b3Q7U2NlbmFyaW8gI2k6JnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWIyZTRcdWM3NGNcdWM1ZDAsIFx1YzhmY1x1YWUzMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc1NDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFeHRyYSBUZXJyZXN0cmlhbCBQSVNBIFRlc3QiLCJkZXNjcmlwdGlvbiI6IjxwPk9uIHRoZSBwbGFuZXQgRGl2aWRvIHRlYWNoZXJzIGhhdmUgYSBzZXJpb3VzIHByb2JsZW0uIER1ZSB0byB0aGUgc3ByZWFkIG9mIGNhbGN1bGF0b3JzIHRoZSBzdHVkZW50cyBjYW5ub3QgZG8gbG9uZyBkaXZpc2lvbiB3aXRoIHBlbmNpbCBhbmQgcGFwZXIgYW55IGxvbmdlci4gQnV0IG5vdyB0aGUgcGxhbmV0YXJpYW4gZ292ZXJubWVudCBoYXMgYW5ub3VuY2VkIGEgdGVzdCBmb3IgYWxsIHN0dWRlbnRzIGluIGJhc2ljIHNjaG9vbHMgdG8gdGVzdCB0aGVpciBtYXRoIHNraWxscy4gQmVjYXVzZSBpdCBoYXMgdG8gYmUgYSBtdWx0aXBsZSBjaG9pY2UgdGVzdCB0aGUgc3R1ZGVudHMgb25seSBoYXZlIHRvIGNhbGN1bGF0ZSB0aGUgbGVuZ3RoIG9mIHRoZSBwZXJpb2Qgd2hlbiBkaXZpZGluZyB0d28gbnVtYmVycy4gWW91ciB0YXNrIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCBjYWxjdWxhdGVzIHRoZSByaWdodCBzb2x1dGlvbnMgaW4gYWR2YW5jZSB0byBlYXNlIHRoZSBjb3JyZWN0aW9uIG9mIHRoZSB0ZXN0LiBBbiBhZGRpdGlvbmFsIHByb2JsZW0gb2NjdXJzIGJlY2F1c2Ugbm90IGFsbCBpbnRlbGxpZ2VudCBzcGVjaWVzIG9uIERpdmlkbyBoYXZlIHRoZSBzYW1lIG51bWJlciBvZiBcdWZiMDFuZ2VycyBhbmQgdGh1cyB0aGVpciBzeXN0ZW1zIG9mIG51bWJlcnMgaGF2ZSBkaWZmZXJlbnQgYmFzZXMuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBiYXNlIFxcKGJcXCksIGEgbnVtZXJhdG9yIFxcKHhcXCksIGFuZCBhIGRlbm9taW5hdG9yIFxcKHlcXCksIHRoZSBsYXR0ZXIgb2Ygd2hpY2ggYXJlIGludGVnZXJzIHRvIHRoZSBiYXNlIFxcKGJcXCkuIFRoZW4gY2FsY3VsYXRlIHRoZSBsZW5ndGggb2YgdGhlIHBlcmlvZCBpbiB0aGUgYmFzZSBcXChiXFwpIGV4cGFuc2lvbiBvZiB0aGUgZnJhY3Rpb24gXFwocSA9IFxcZnJhY3t4fXt5fVxcKS4gUmVtZW1iZXIgdGhhdCB0aGUgZGlnaXRzIG9mIHRoZSBiYXNlIFxcKGJcXCkgZXhwYW5zaW9uIG9mIHRoZSB0aGUgcmF0aW9uYWwgbnVtYmVyIFxcKHFcXCkgYXJlIHRoZSBjb2VmXHVmYjAxY2llbnRzIG9mIHRoZSBwb3dlcnMgb2YgdGhlIGJhc2U6PFwvcD5cclxuXHJcbjxwPlxcKHE9cV97bn1xX3tuLTF9XFxkb3RzIHFfezB9LnFfey0xfXFfey0yfSBcXGRvdHMgPSBcXHN1bSBfe2k9LVxcaW5mdHkgfSBee259e3FfaWJeaX1cXCk8XC9wPlxyXG5cclxuPHA+SGVyZSBhcmUgc29tZSBleGFtcGxlczo8XC9wPlxyXG5cclxuPHA+XFwoXFxmcmFjIHsxX3sxMH19ezJfezEwfX0gPSAwLjVfezEwfVxcKSwgXFwoXFxmcmFjIHsxXzN9IHsxMF8zfSA9IDAuMV8zXFwpLCBcXChcXGZyYWMgezJfezEwfX17MTFfezEwfX0gPSAwLjE4MTgxOFxcZG90c197MTB9ID0gMC5cXG92ZXJsaW5lIHsgMTggfSAmbmJzcDtfezEwfVxcKTxcL3A+XHJcblxyXG48cD5JbiB0aGUgXHVmYjAxcnN0IHR3byBleGFtcGxlcywgdGhlcmUgaXMgYSBcdWZiMDFuaXRlIGJhc2UgXFwoYlxcKSBleHBhbnNpb24gb2YgdGhlIGZyYWN0aW9uLCBtZWFuaW5nIHRoYXQgYWxsIGRpZ2l0cyB0aGF0IGZvbGxvdyBhcmUgemVyby4gSW4gdGhhdCBjYXNlLCB3ZSBzYXkgdGhhdCB0aGUgbGVuZ3RoIG9mIHRoZSBwZXJpb2QgaXMgemVyby4gTm90ZSB0aGF0IG9uZSBjb3VsZCBhcyB3ZWxsIGV4cHJlc3MgdGhlIFx1ZmIwMXJzdCBleGFtcGxlIGFzIFxcKDAuNFxcb3ZlcmxpbmUgeyA5IH0gX3sgMTAgfVxcKSB3aXRoIGEgcGVyaW9kIGxlbmd0aCBvZiBvbmUsIGJ1dCB0aGF0IGlzIG5vdCB3aGF0IHdlIHdhbnQuPFwvcD5cclxuXHJcbjxwPkluIHRoZSB0aGlyZCBleGFtcGxlLCBob3dldmVyLCB0aGUgcGVyaW9kIGxlbmd0aCBpcyB1bmFtYmlndW91c2x5IHR3by48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIGZyYWN0aW9ucy4gRm9yIGVhY2ggZnJhY3Rpb24geW91IGFyZSBcdWZiMDFyc3QgZ2l2ZW4gdGhlIGJhc2UgXFwoYlxcKSBhcyBhIGRlY2ltYWwgbnVtYmVyIHdpdGggMiAmbGU7IFxcKGJcXCkgJmxlOyAzNiwgYW5kIHRoZW4gdGhlIG51bWVyYXRvciBcXCh4XFwpIGFuZCB0aGUgZGVub21pbmF0b3IgXFwoeVxcKSBvZiB0aGUgZnJhY3Rpb24gdG8gdGhhdCBiYXNlIHNlcGFyYXRlZCBieSBzaW5nbGUgYmxhbmtzLiBJdCBpcyBndWFyYW50ZWVkIHRoYXQgdGhlIGRlbm9taW5hdG9yIHNhdGlzXHVmYjAxZXMgMCAmbHQ7IFxcKHlcXCkgJmxlOyAxMDAgMDAwPHN1Yj4xMDxcL3N1Yj4uIERpZ2l0cyBub3QgaW4gdGhlIHJhbmdlIG9mIDAuLi45IGFyZSByZXByZXNlbnRlZCBieSBsZXR0ZXJzIHN0YXJ0aW5nIGZyb20gJmxkcXVvO2EmcmRxdW87IG9yICZsZHF1bztBJnJkcXVvOyBpbiB0aGUgdXN1YWwgd2F5LCB3aGVyZSBjYXNlIGRvZXMgbm90IG1hdHRlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZvciBldmVyeSBzY2VuYXJpbyBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyAmbGRxdW87U2NlbmFyaW8gI2k6JnJkcXVvOywgd2hlcmUgaSBpcyB0aGUgbnVtYmVyIG9mIHRoZSBzY2VuYXJpbyBzdGFydGluZyBhdCAxLiBUaGVuIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbGVuZ3RoIG9mIHRoZSBwZXJpb2QgaW4gdGhlIGJhc2UgXFwoYlxcKSBleHBhbnNpb24gb2YgXFwoXFxmcmFje3h9e3l9XFwpICwgYnV0IG1ha2Ugc3VyZSB0byBwcmludCB0aGUgbGVuZ3RoIGFzIGEgZGVjaW1hbCBudW1iZXIuIFRlcm1pbmF0ZSB0aGUgb3V0cHV0IGZvciB0aGUgc2NlbmFyaW8gd2l0aCBhIGJsYW5rIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d