시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 302 49 40 21.978%

문제

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

팩토리얼 진영의 유명한 장군 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+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHViNTRjLCBuIVx1Yzc0NCBrPHN1cD5pPFwvc3VwPlx1Yjg1YyBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVkMDcwIGlcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFQgJmxlOyAxMDApIFx1YjJlNFx1Yzc0YyBUXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhY2ZjIGtcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgbiAmbGU7IDEwPHN1cD4xODxcL3N1cD4sIDIgJmxlOyAmbmJzcDtrICZsZTsgMTA8c3VwPjEyPFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWQwNzAgaVx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk2NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZhY3VsdHkgRGl2aWRpbmcgUG93ZXJzIiwiZGVzY3JpcHRpb24iOiI8cD5GcmVkIEZhY3VsdHkgYW5kIFBhdWwgUG93ZXIgbG92ZSBiaWcgbnVtYmVycy4gRGF5IGFmdGVyIGRheSBGcmVkIGNob29zZXMgYSByYW5kb20gaW50ZWdlciBuIGFuZCBoZSBjb21wdXRlcyBuIS4gSGlzIGZyaWVuZCBQYXVsIGFtdXNlcyBoaW1zZWxmIGJ5IGNvbXB1dGluZyBzZXZlcmFsIHBvd2VycyBvZiBoaXMgcmFuZG9tbHkgY2hvc2VuIGludGVnZXIgayBsaWtlIGs8c3VwPjI8XC9zdXA+LCBrPHN1cD4zPFwvc3VwPiwgLi4uIGFuZCBzbyBvbi4gT24gYSBob3Qgc3VtbWVyIGRheSwgRnJlZCBhbmQgUGF1bCBnb3QgcmVhbGx5LCByZWFsbHkgYm9yZWQsIHNvIHRoZXkgZGVjaWRlZCB0byBwbGF5IGEgam9rZSBvbiB0aGVpciBidWRkeSBEYXZlIERpdmlkZXIuIEZyZWQgY2hvb3NlcyBhIHJhbmRvbSBpbnRlZ2VyIG4gd2hpbGUgUGF1bCBjaG9vc2VzIGEgcmFuZG9tIGludGVnZXIgay4gVGhleSB3YW50IERhdmUgdG8gZmluZCB0aGUgYmlnZ2VzdCBpbnRlZ2VyIGkgc3VjaCB0aGF0IGtpIGRpdmlkZXMgbiEgd2l0aG91dCBhIHJlbWFpbmRlciwgb3RoZXJ3aXNlIHRoZXkgd2lsbCB0aHJvdyBhIGNha2UgaW4gRGF2ZSYjMzk7cyBmYWNlLiBCZWNhdXNlIERhdmUgZG9lcyBub3QgbGlrZSBjYWtlcyBpbiBoaXMgZmFjZSwgaGUgd2FudHMgeW91IHRvIGhlbHAgaGltIGZpbmRpbmcgdGhhdCBpbnRlZ2VyIGkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdCZuYnNwOygxICZsZTsgVCAmbGU7IDEwMCkuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyB0IGxpbmVzIGNvbnRhaW5zIHRoZSB0d28gbnVtYmVycyBuLCZuYnNwO2sgKDIgJmxlOyBuICZsZTsgMTA8c3VwPjE4PFwvc3VwPiwgMiAmbGU7ICZuYnNwO2sgJmxlOyAxMDxzdXA+MTI8XC9zdXA+KSBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIG1heGltdW0gaW50ZWdlciBpIG9uIGEgc2VwYXJhdGUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=