Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

PAGAIN3 - Previous Prime (128 bit edition)

no tags 

http://infosthetics.com/archives/2009/12/visualizing_prime_numbers.html

In this problem, you have to find the nearest prime number smaller than N.

Input

The first line contains an integer T specifying the number of test cases.

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

Constraints

3 <= N <= 2^128
0 < T < 10^5

Information

Input is not randomly chosen.
Prime Again and Previous prime (64 bit edition) are recommended problems before this one.
Time limit is twice the time given by my deterministic_Python_code, but the input file is way too small, so there's still some weakness, and much faster code can get AC... Have fun ;-)

Under construction - please be patient


Added by:Francky
Date:2014-12-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64