시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 408 132 112 39.298%

문제

정수 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 이다.

W3sicHJvYmxlbV9pZCI6Ijk3NTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZGQgXHVhY2YxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMTggSyAoMSAmbGU7IEsgJmxlOyAxMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIEtcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjZjEgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhY2YxXHVjNzQ0Jm5ic3A7XHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKDEgJmxlOyBUICZsZTsgMjApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFRcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IEtcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBLXHViOWM4XHViMmU0IEtcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWMxOGNcdWMyMThcdWM3NTggXHVhY2YxIFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWNmMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPks9MVx1Yzc3OCBcdWFjYmRcdWM2YjAgXHViMmY1XHVjNzQwIDYgPSAyICZ0aW1lczsgM1x1Yzc3NFx1YjJlNC4gNlx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWMxOGNcdWMyMThcdWM3NTggXHVhY2YxIFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWNmMVx1Yzc3NFx1YjJlNC4gNCA9IDIgJnRpbWVzOyAyIFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxYyBLPTEwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM4MTVcdWIyZjVcdWM3NDAgMTAgPSAyICZ0aW1lczsgNSBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM2MDhcdWM4MWMgSz0xMDAwMDBcdWM3NzggXHVhY2JkXHVjNmIwIFx1YzgxNVx1YjJmNVx1Yzc0MCAxMDAwMDEgPSAxMSAmdGltZXM7IDkwOTEgXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTc1MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik11bHRpcGx5aW5nIFBhaXJzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhbiBpbnRlZ2VyIEsgKDEgJmx0Oz0gSyAmbHQ7PSAxMDAsMDAwKSwgZmluZCB0aGUgc21hbGxlc3QgaW50ZWdlciBubyBsZXNzIHRoYW4gSyB3aGljaCBpcyBhIHByb2R1Y3Qgb2YgZXhhY3RseSB0d28gZGlmZmVyZW50IHByaW1lIG51bWJlcnMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgc3BlY2lmaWVzIGFuIGludGVnZXIgVCAoMSAmbHQ7PSBUICZsdDs9IDIwKSwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGVuIFQgbGluZXMgZm9sbG93LCBlYWNoIGxpbmUgY29udGFpbmluZyBvbmUgdGVzdCBjYXNlLiBFYWNoIHRlc3QgY2FzZSBzcGVjaWZpZXMgb25lIGludGVnZXIgSy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGhhcyBUIGxpbmVzLCBlYWNoIGZvciBlYWNoIHRlc3QgY2FzZS4gRWFjaCBsaW5lIHNob3VsZCBzcGVjaWZ5IHRoZSBzbWFsbGVzdCBpbnRlZ2VyIG5vIGxlc3MgdGhhbiBLIHdoaWNoIGlzIGEgcHJvZHVjdCBvZiBleGFjdGx5IHR3byBkaWZmZXJlbnQgcHJpbWUgbnVtYmVycy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGZpcnN0IGV4YW1wbGUgd2hlcmUgSz0xLCB0aGUgYW5zd2VyIGlzIDYgYmVjYXVzZSA2ID0gMiB4IDMgYW5kIGl0IGlzIHRoZSBzbWFsbGVzdCBpbnRlZ2VyIHdoaWNoIGlzIGEgcHJvZHVjdCBvZiBleGFjdGx5IHR3byBkaWZmZXJlbnQgcHJpbWUgbnVtYmVycy4gTm90ZSB0aGF0IDQgaXMgbm90IHRoZSBhbnN3ZXIgYmVjYXVzZSA0ID0gMiB4IDIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoZSB0aGlyZCBleGFtcGxlIHdoZXJlIEs9MTAsIHRoZSBhbnN3ZXIgaXMgMTAgYmVjYXVzZSAxMCBpcyBhIHByb2R1Y3Qgb2YgMiBhbmQgNSwgYm90aCBvZiB3aGljaCBhcmUgcHJpbWUgbnVtYmVycyBhbmQgMiBhbmQgNSBhcmUgZGlmZmVyZW50LiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0aGUgbGFzdCBleGFtcGxlIHdoZXJlIEs9MTAwMDAwLCB0aGUgYW5zd2VyIGlzIDEwMDAwMSBiZWNhdXNlIDEwMDAwMSBpcyBhIHByb2R1Y3Qgb2YgMTEgYW5kIDkwOTEsIGJvdGggb2Ygd2hpY2ggYXJlIHByaW1lIG51bWJlcnMgYW5kIDIgYW5kIDUgYXJlIGRpZmZlcmVudC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==