시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 475 155 131 38.757%

문제

정수 K (1 ≤ K ≤ 100,000)가 주어진다. 이때, K보다 크거나 같은 서로 다른 소수의 곱 중에서 가장 작은 곱을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 다음 T개 줄에는 K가 한 줄에 하나씩 주어진다. 

출력

각각의 K마다 K보다 크거나 같은 서로 다른 두 소수의 곱 중에서 가장 작은 곱을 출력한다.

예제 입력 1

5
1
3
10
300
100000

예제 출력 1

6
6
10
301
100001

힌트

K=1인 경우 답은 6 = 2 × 3이다. 6은 서로 다른 두 소수의 곱 중에서 가장 작은 곱이다. 4 = 2 × 2 이기 때문에, 정답이 되지 않는다.

세 번째 예제 K=10인 경우에 정답은 10 = 2 × 5 이다.

마지막 예제 K=100000인 경우 정답은 100001 = 11 × 9091 이다.

W3sicHJvYmxlbV9pZCI6Ijk3NTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZGQgXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMTggSyAoMSAmbGU7IEsgJmxlOyAxMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgS1x1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMThjXHVjMjE4XHVjNzU4IFx1YWNmMSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjZjFcdWM3NDQmbmJzcDtcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoMSAmbGU7IFQgJmxlOyAyMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgVFx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgS1x1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IEtcdWI5YzhcdWIyZTQgS1x1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjZjEgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhY2YxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+Sz0xXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWIyZjVcdWM3NDAgNiA9IDIgJnRpbWVzOyAzXHVjNzc0XHViMmU0LiA2XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjZjEgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhY2YxXHVjNzc0XHViMmU0LiA0ID0gMiAmdGltZXM7IDIgXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjODE1XHViMmY1XHVjNzc0IFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjIEs9MTBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzgxNVx1YjJmNVx1Yzc0MCAxMCA9IDIgJnRpbWVzOyA1IFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzYwOFx1YzgxYyBLPTEwMDAwMFx1Yzc3OCBcdWFjYmRcdWM2YjAgXHVjODE1XHViMmY1XHVjNzQwIDEwMDAwMSA9IDExICZ0aW1lczsgOTA5MSBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NzUzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTXVsdGlwbHlpbmcgUGFpcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGFuIGludGVnZXIgSyAoMSAmbHQ7PSBLICZsdDs9IDEwMCwwMDApLCBmaW5kIHRoZSBzbWFsbGVzdCBpbnRlZ2VyIG5vIGxlc3MgdGhhbiBLIHdoaWNoIGlzIGEgcHJvZHVjdCBvZiBleGFjdGx5IHR3byBkaWZmZXJlbnQgcHJpbWUgbnVtYmVycy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBzcGVjaWZpZXMgYW4gaW50ZWdlciBUICgxICZsdDs9IFQgJmx0Oz0gMjApLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIFRoZW4gVCBsaW5lcyBmb2xsb3csIGVhY2ggbGluZSBjb250YWluaW5nIG9uZSB0ZXN0IGNhc2UuIEVhY2ggdGVzdCBjYXNlIHNwZWNpZmllcyBvbmUgaW50ZWdlciBLLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgaGFzIFQgbGluZXMsIGVhY2ggZm9yIGVhY2ggdGVzdCBjYXNlLiBFYWNoIGxpbmUgc2hvdWxkIHNwZWNpZnkgdGhlIHNtYWxsZXN0IGludGVnZXIgbm8gbGVzcyB0aGFuIEsgd2hpY2ggaXMgYSBwcm9kdWN0IG9mIGV4YWN0bHkgdHdvIGRpZmZlcmVudCBwcmltZSBudW1iZXJzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgZXhhbXBsZSB3aGVyZSBLPTEsIHRoZSBhbnN3ZXIgaXMgNiBiZWNhdXNlIDYgPSAyIHggMyBhbmQgaXQgaXMgdGhlIHNtYWxsZXN0IGludGVnZXIgd2hpY2ggaXMgYSBwcm9kdWN0IG9mIGV4YWN0bHkgdHdvIGRpZmZlcmVudCBwcmltZSBudW1iZXJzLiBOb3RlIHRoYXQgNCBpcyBub3QgdGhlIGFuc3dlciBiZWNhdXNlIDQgPSAyIHggMi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gdGhlIHRoaXJkIGV4YW1wbGUgd2hlcmUgSz0xMCwgdGhlIGFuc3dlciBpcyAxMCBiZWNhdXNlIDEwIGlzIGEgcHJvZHVjdCBvZiAyIGFuZCA1LCBib3RoIG9mIHdoaWNoIGFyZSBwcmltZSBudW1iZXJzIGFuZCAyIGFuZCA1IGFyZSBkaWZmZXJlbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoZSBsYXN0IGV4YW1wbGUgd2hlcmUgSz0xMDAwMDAsIHRoZSBhbnN3ZXIgaXMgMTAwMDAxIGJlY2F1c2UgMTAwMDAxIGlzIGEgcHJvZHVjdCBvZiAxMSBhbmQgOTA5MSwgYm90aCBvZiB3aGljaCBhcmUgcHJpbWUgbnVtYmVycyBhbmQgMiBhbmQgNSBhcmUgZGlmZmVyZW50LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d