PAGAIN - Prime Again

no tags 

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/pagain


In this problem, you have to find the nearest prime number smaller than N. (3 <= N <= 2^32)

Input

The first line contains an integer T specifying the number of test cases. (T <= 10000)

T lines follow, each line contains an integer N.

Output

For each test case, output the result on one line.

Example

Input:
3
5 
10
17

Output:
3
7
13


Added by:Race with time
Date:2008-12-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET