시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB163426019617.900%

문제

수학 나라에 전쟁이 일어났다. 팩토리얼 진영과 거듭제곱 진영은 누가 수학 나라를 지배할 것인지 결정하기 위해 싸우고 있다.

팩토리얼 진영의 유명한 장군 n은 자기 자신을 팩토리얼 계산을 하면서 훈련을 하고 있고, 거듭제곱진영의 제독 k는 자기 자신에 i제곱을 하기 위해 i를 만들고 있었다.

드디어 오늘은 n과 k가 싸우는 날이다. k는 n을 나누어서 작은 수로 만들어 버리기 위해서 몇 년동안 훈련을 진행하고 있었다.

이제 k는 n을 나누려고 한다. 훈련을 통해서 모두 성장했으므로, n!와 ki와 싸우는 것이다.

이때, n!을 ki로 나눌 수 있는 가장 큰 i를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 100) 다음 T개의 줄에는 n과 k가 공백으로 구분되어 주어진다. (2 ≤ n ≤ 1018, 2 ≤  k ≤ 1012)

출력

각각의 테스트 케이스에 대해서, 가장 큰 i를 한 줄에 하나씩 출력한다.

예제 입력 1

2
5 2
10 10

예제 출력 1

3
2
W3sicHJvYmxlbV9pZCI6IjM5NjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMjlcdWQxYTBcdWI5YWNcdWM1YmNcdWFjZmMgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMyMThcdWQ1NTkgXHViMDk4XHViNzdjXHVjNWQwIFx1YzgwNFx1YzdjMVx1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwYWNcdWIyZTQuIFx1ZDMyOVx1ZDFhMFx1YjlhY1x1YzViYyBcdWM5YzRcdWM2MDFcdWFjZmMgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxIFx1YzljNFx1YzYwMVx1Yzc0MCBcdWIyMDRcdWFjMDAgXHVjMjE4XHVkNTU5IFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWM5YzBcdWJjMzBcdWQ1NjAgXHVhYzgzXHVjNzc4XHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMmY4XHVjNmIwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMzI5XHVkMWEwXHViOWFjXHVjNWJjIFx1YzljNFx1YzYwMVx1Yzc1OCBcdWM3MjBcdWJhODVcdWQ1NWMgXHVjN2E1XHVhZDcwIG5cdWM3NDAgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc0NCBcdWQzMjlcdWQxYTBcdWI5YWNcdWM1YmMgXHVhY2M0XHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YmE3NFx1YzExYyBcdWQ2YzhcdWI4MjhcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVhYzcwXHViNGVkXHVjODFjXHVhY2YxXHVjOWM0XHVjNjAxXHVjNzU4IFx1YzgxY1x1YjNjNSBrXHViMjk0IFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM1ZDAgaVx1YzgxY1x1YWNmMVx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IGlcdWI5N2MgXHViOWNjXHViNGU0XHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViNGRjXHViNTE0XHVjNWI0IFx1YzYyNFx1YjI5OFx1Yzc0MCBuXHVhY2ZjIGtcdWFjMDAgXHVjMmY4XHVjNmIwXHViMjk0IFx1YjBhMFx1Yzc3NFx1YjJlNC4ga1x1YjI5NCBuXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YzViNFx1YzExYyBcdWM3OTFcdWM3NDAgXHVjMjE4XHViODVjIFx1YjljY1x1YjRlNFx1YzViNCBcdWJjODRcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YmE4NyBcdWIxNDRcdWIzZDlcdWM1NDggXHVkNmM4XHViODI4XHVjNzQ0IFx1YzljNFx1ZDU4OVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NFx1YzgxYyBrXHViMjk0IG5cdWM3NDQgXHViMDk4XHViMjA0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNmM4XHViODI4XHVjNzQ0IFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWJhYThcdWI0NTAgXHVjMTMxXHVjN2E1XHVkNTg4XHVjNzNjXHViYmMwXHViODVjLCBuIVx1YzY0MCBrPHN1cD5pPFwvc3VwPlx1YzY0MCBcdWMyZjhcdWM2YjBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzRcdWI1NGMsIG4hXHVjNzQ0IGs8c3VwPmk8XC9zdXA+XHViODVjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWQwNzAgaVx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgVCAmbGU7IDEwMCkgXHViMmU0XHVjNzRjIFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjZmMga1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgMTA8c3VwPjE4PFwvc3VwPiwgMiAmbGU7ICZuYnNwO2sgJmxlOyAxMDxzdXA+MTI8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAwXHVjN2E1IFx1ZDA3MCBpXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzOTY0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmFjdWx0eSBEaXZpZGluZyBQb3dlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkZyZWQgRmFjdWx0eSBhbmQgUGF1bCBQb3dlciBsb3ZlIGJpZyBudW1iZXJzLiBEYXkgYWZ0ZXIgZGF5IEZyZWQgY2hvb3NlcyBhIHJhbmRvbSBpbnRlZ2VyIG4gYW5kIGhlIGNvbXB1dGVzIG4hLiBIaXMgZnJpZW5kIFBhdWwgYW11c2VzIGhpbXNlbGYgYnkgY29tcHV0aW5nIHNldmVyYWwgcG93ZXJzIG9mIGhpcyByYW5kb21seSBjaG9zZW4gaW50ZWdlciBrIGxpa2UgazxzdXA+MjxcL3N1cD4sIGs8c3VwPjM8XC9zdXA+LCAuLi4gYW5kIHNvIG9uLiBPbiBhIGhvdCBzdW1tZXIgZGF5LCBGcmVkIGFuZCBQYXVsIGdvdCByZWFsbHksIHJlYWxseSBib3JlZCwgc28gdGhleSBkZWNpZGVkIHRvIHBsYXkgYSBqb2tlIG9uIHRoZWlyIGJ1ZGR5IERhdmUgRGl2aWRlci4gRnJlZCBjaG9vc2VzIGEgcmFuZG9tIGludGVnZXIgbiB3aGlsZSBQYXVsIGNob29zZXMgYSByYW5kb20gaW50ZWdlciBrLiBUaGV5IHdhbnQgRGF2ZSB0byBmaW5kIHRoZSBiaWdnZXN0IGludGVnZXIgaSBzdWNoIHRoYXQga2kgZGl2aWRlcyBuISB3aXRob3V0IGEgcmVtYWluZGVyLCBvdGhlcndpc2UgdGhleSB3aWxsIHRocm93IGEgY2FrZSBpbiBEYXZlJiMzOTtzIGZhY2UuIEJlY2F1c2UgRGF2ZSBkb2VzIG5vdCBsaWtlIGNha2VzIGluIGhpcyBmYWNlLCBoZSB3YW50cyB5b3UgdG8gaGVscCBoaW0gZmluZGluZyB0aGF0IGludGVnZXIgaS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0Jm5ic3A7KDEgJmxlOyBUICZsZTsgMTAwKS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIHQgbGluZXMgY29udGFpbnMgdGhlIHR3byBudW1iZXJzIG4sJm5ic3A7ayAoMiAmbGU7IG4gJmxlOyAxMDxzdXA+MTg8XC9zdXA+LCAyICZsZTsgJm5ic3A7ayAmbGU7IDEwPHN1cD4xMjxcL3N1cD4pIHNlcGFyYXRlZCBieSBvbmUgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCB0aGUgbWF4aW11bSBpbnRlZ2VyIGkgb24gYSBzZXBhcmF0ZSBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=