4517 - 가까운 소수

• Submit
• Status
• Discuss
• Summary

Description

소수(素數; prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.

N과 가장 가까운 소수를 찾아보자.

만약 가장 가까운 소수가 1개 이상이라면 오름차순으로 전부 출력한다.

Input

* Line 1 : 입력의 갯수 N이 입력된다. (1 ≤ N ≤ 1000)

* Line 2~N+1: 자연수 n이 입력된다. (1 ≤ n ≤ 2000000)

Output

* Line 1~N : n과 가장 가까운 소수를 출력한다.

Sample Input

3
5
6
100

Sample Output

5
5 7
101