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

입력 형식

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

출력 형식

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

예제 입력

5
1
3
10
300
100000

예제 출력

6
6
10
301
100001

힌트

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

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

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