시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 7 6 6 85.714%

문제

구글은 실리콘밸리 중심가 101번 고속도로가 통과하는 곳에 다음과 같은 광고판을 달았다.

 

"{first 10-digit prime found in consecutive digits of e}.com"

 

구글의 채용 방법에 크게 감동한 구강 청정제 회사 가글에서는 다음과 같은 문제로 사람을 뽑으려고 한다.

 

{어떤 유리수를 7진법으로 나타낸 뒤, 소수점 B번째 자리부터 E번째 자리까지}.com

 

예를 들어, 1/510를 7진법으로 나타내면 0.12541...7, 33/410는 11.15151...7, 6/4910은 0.06000...7이다.

유리수가 주어졌을 때, 이 유리수의 소수점 B번째 자리부터 E번쨰 자리까지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 N, D, B, E가 10진수로 한 줄에 하나씩 주어진다. N과 D는 유리수의 분자와 분모이고, 0 ≤ N ≤ 5,000, 1 ≤ D ≤ 5,000을 만족한다. B와 E는 구해야 하는 수의 범위이다. 0 ≤ B,E ≤ 250, 0 ≤ (E-B) ≤ 20을 만족한다. 소수점 0번째 자리는 소수점 바로 오른쪽에 있는 수이다.

출력

각 테스트 케이스에 대해서, 다음과 같이 출력한다.

Problem set k: N / D, base 7 digits B through E: result

k는 테스트 케이스 번호, result는 계산한 값, 다른 값은 입력에 주어진 값이다.

예제 입력 1

4
1 5 0 0
6 49 1 3
33 4 2 7
511 977 122 126

예제 출력 1

Problem set 1: 1 / 5, base 7 digits 0 through 0: 1
Problem set 2: 6 / 49, base 7 digits 1 through 3: 600
Problem set 3: 33 / 4, base 7 digits 2 through 7: 151515
Problem set 4: 511 / 977, base 7 digits 122 through 126: 12425

힌트

W3sicHJvYmxlbV9pZCI6IjQ2MjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWFlMDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWQ2Y1x1YWUwMFx1Yzc0MCBcdWMyZTRcdWI5YWNcdWNmNThcdWJjMzhcdWI5YWMgXHVjOTExXHVjMmVjXHVhYzAwIDEwMVx1YmM4OCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWFjMDAgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0IFx1YWNmM1x1YzVkMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWQxMVx1YWNlMFx1ZDMxMFx1Yzc0NCBcdWIyZWNcdWM1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcblxyXG48YmxvY2txdW90ZT4mcXVvdDt7Zmlyc3QgMTAtZGlnaXQgcHJpbWUgZm91bmQgaW4gY29uc2VjdXRpdmUgZGlnaXRzIG9mIGV9LmNvbSZxdW90OzxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVhZTAwXHVjNzU4IFx1Y2M0NFx1YzZhOSBcdWJjMjlcdWJjOTVcdWM1ZDAgXHVkMDZjXHVhYzhjIFx1YWMxMFx1YjNkOVx1ZDU1YyBcdWFkNmNcdWFjMTUgXHVjY2FkXHVjODE1XHVjODFjIFx1ZDY4Y1x1YzBhYyBcdWFjMDBcdWFlMDBcdWM1ZDBcdWMxMWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM4MWNcdWI4NWMgXHVjMGFjXHViNzhjXHVjNzQ0IFx1YmY1MVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcblxyXG48YmxvY2txdW90ZT57XHVjNWI0XHViNWE0IFx1YzcyMFx1YjlhY1x1YzIxOFx1Yjk3YyA3XHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWI0YTQsIFx1YzE4Y1x1YzIxOFx1YzgxMCBCXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YmQ4MFx1ZDEzMCBFXHViYzg4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMH0uY29tPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAxXC81PHN1Yj4xMDxcL3N1Yj5cdWI5N2MgN1x1YzljNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzQgMC4xMjU0MS4uLjxzdWI+NzxcL3N1Yj4sIDMzXC80PHN1Yj4xMDxcL3N1Yj5cdWIyOTQgMTEuMTUxNTEuLi48c3ViPjc8XC9zdWI+LCA2XC80OTxzdWI+MTA8XC9zdWI+XHVjNzQwIDAuMDYwMDAuLi48c3ViPjc8XC9zdWI+XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWI5YWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzcyMFx1YjlhY1x1YzIxOFx1Yzc1OCBcdWMxOGNcdWMyMThcdWM4MTAgQlx1YmM4OFx1YzlmOCBcdWM3OTBcdWI5YWNcdWJkODBcdWQxMzAgRVx1YmM4OFx1Y2EzMCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBOLCBELCBCLCBFXHVhYzAwIDEwXHVjOWM0XHVjMjE4XHViODVjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1YWNmYyBEXHViMjk0IFx1YzcyMFx1YjlhY1x1YzIxOFx1Yzc1OCBcdWJkODRcdWM3OTBcdWM2NDAgXHViZDg0XHViYWE4XHVjNzc0XHVhY2UwLCAwICZsZTsgTiAmbGU7IDUsMDAwLCAxICZsZTsgRCAmbGU7IDUsMDAwXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gQlx1YzY0MCBFXHViMjk0IFx1YWQ2Y1x1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjMjE4XHVjNzU4IFx1YmM5NFx1YzcwNFx1Yzc3NFx1YjJlNC4gMCAmbGU7IEIsRSAmbGU7IDI1MCwgMCAmbGU7IChFLUIpICZsZTsgMjBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LiBcdWMxOGNcdWMyMThcdWM4MTAgMFx1YmM4OFx1YzlmOCBcdWM3OTBcdWI5YWNcdWIyOTQgXHVjMThjXHVjMjE4XHVjODEwIFx1YmMxNFx1Yjg1YyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5Qcm9ibGVtIHNldCBrOiBOIFwvIEQsIGJhc2UgNyBkaWdpdHMgQiB0aHJvdWdoIEU6IHJlc3VsdDxcL3ByZT5cclxuXHJcbjxwPmtcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzgsIHJlc3VsdFx1YjI5NCBcdWFjYzRcdWMwYjBcdWQ1NWMgXHVhYzEyLCBcdWIyZTRcdWI5NzggXHVhYzEyXHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhYzEyXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ2MjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb25zZWN1dGl2ZSBEaWdpdHMiLCJkZXNjcmlwdGlvbiI6IjxwPkFzIGEgcmVjcnVpdGluZyBwbG95LCBHb29nbGUgb25jZSBwb3N0ZWQgYmlsbGJvYXJkcyBpbiBIYXJ2YXJkIFNxdWFyZSBhbmQgaW4gdGhlIFNpbGljb24gVmFsbGV5IGFyZWEganVzdCBzdGF0aW5nICZsZHF1bzt7Zmlyc3QgMTAtZGlnaXQgcHJpbWUgZm91bmQgaW4gY29uc2VjdXRpdmUgZGlnaXRzIG9mIGV9LmNvbSZyZHF1bzsuIEluIG90aGVyIHdvcmRzLCBmaW5kIHRoYXQgMTAtZGlnaXQgc2VxdWVuY2UgYW5kIHRoZW4gY29ubmVjdCB0byB0aGUgd2ViIHNpdGUgJm1kYXNoOyBhbmQgZmluZCBvdXQgdGhhdCBHb29nbGUgaXMgdHJ5aW5nIHRvIGhpcmUgcGVvcGxlIHdobyBjYW4gc29sdmUgYSBwYXJ0aWN1bGFyIGtpbmQgb2YgcHJvYmxlbS48XC9wPlxyXG5cclxuPHA+Tm90IHRvIGJlIG91dGRvbmUsIEdhZ2dsZSAoYSBsb29zeS1nb29zeSBmdXp6eSBsb2dpYyBzZWFyY2ggZmlybSksIGhhcyBkZXZpc2VkIGl0cyBvd24gcmVjcnVpdGluZyBwcm9ibGVtLiBDb25zaWRlciB0aGUgYmFzZSA3IGV4cGFuc2lvbiBvZiBhIHJhdGlvbmFsIG51bWJlci4gRm9yIGV4YW1wbGUsIHRoZSBmaXJzdCBmZXcgZGlnaXRzIG9mIHRoZSBiYXNlIDcgZXhwYW5zaW9uIG9mIDFcLzU8c3ViPjEwPFwvc3ViPiA9IDAuMTI1NDEuLi48c3ViPjc8XC9zdWI+LCAzM1wvNDxzdWI+MTA8XC9zdWI+ID0gMTEuMTUxNTEuLi48c3ViPjc8XC9zdWI+LCBhbmQgNlwvNDk8c3ViPjEwPFwvc3ViPiA9IDAuMDYwMDAuLi48c3ViPjc8XC9zdWI+LCBGcm9tIHRoaXMgZXhwYW5zaW9uLCBmaW5kIHRoZSBkaWdpdHMgaW4gYSBwYXJ0aWN1bGFyIHJhbmdlIG9mIHBvc2l0aW9ucyB0byB0aGUgcmlnaHQgb2YgdGhlICZxdW90O2RlY2ltYWwmcXVvdDsgcG9pbnQ8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgc3BlY2lmeWluZyB0aGUgbnVtYmVyIG9mIHByb2JsZW0gc2V0cyBpbiB0aGUgZmlsZS4gRWFjaCBwcm9ibGVtIHNldCBpcyBzcGVjaWZpZWQgYnkgZm91ciBiYXNlIDEwIG51bWJlcnMgb24gYSBzaW5nbGUgbGluZSwgbiBkIGIgZSwgd2hlcmUgbiBhbmQgZCBhcmUgdGhlIG51bWVyYXRvciBhbmQgZGVub21pbmF0b3Igb2YgdGhlIHJhdGlvbmFsIG51bWJlciBhbmQgMCAmbGU7IG4gJmxlOyA1LDAwMCBhbmQgMSAmbGU7IGQgJmxlOyA1LDAwMC4gYiBhbmQgZSBhcmUgdGhlIGJlZ2lubmluZyBhbmQgZW5kaW5nIHBvc2l0aW9ucyBmb3IgdGhlIGRlc2lyZWQgcmFuZ2Ugb2YgZGlnaXRzLCB3aXRoIDAgJmxlOyBiLGUgJmxlOyAyNTAgYW5kIDAgJmxlOyAoZS1iKSAmbGU7IDIwLiBOb3RlIHRoYXQgMCBpcyB0aGUgcG9zaXRpb24gaW1tZWRpYXRlbHkgdG8gdGhlIHJpZ2h0IG9mIHRoZSBkZWNpbWFsIHBvaW50LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkVhY2ggcHJvYmxlbSBzZXQgd2lsbCBiZSBudW1iZXJlZCAoYmVnaW5uaW5nIGF0IG9uZSkgYW5kIHdpbGwgZ2VuZXJhdGUgYSBzaW5nbGUgbGluZTo8XC9wPlxyXG5cclxuPHByZT5cclxuUHJvYmxlbSBzZXQgazogbiBcLyBkLCBiYXNlIDcgZGlnaXRzIGIgdGhyb3VnaCBlOiByZXN1bHQ8XC9wcmU+XHJcblxyXG48cD53aGVyZSBrIGlzIHJlcGxhY2VkIGJ5IHRoZSBwcm9ibGVtIHNldCBudW1iZXIsIHJlc3VsdCBpcyB5b3VyIGNvbXB1dGVkIHJlc3VsdCwgYW5kIHRoZSBvdGhlciB2YWx1ZXMgYXJlIHRoZSBjb3JyZXNwb25kaW5nIGlucHV0IHZhbHVlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=