B. Noorhan's Birthday
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Noorhan's birthday is just around the corner, and the excitement is building up! She's been chatting non-stop with her friends Manar and Nagham, dropping hints left and right about how many gifts she'd love to receive this year. The magic number she's been dreaming about is $$$n$$$ gifts.

Manar and Nagham have cooked up a fantastic plan. Instead of just giving her $$$n$$$ gifts, they're going to surprise her with $$$a$$$ gifts, where $$$a$$$ is the closest prime number to $$$n$$$. Help Manar and Nagham decide how many gifts they're getting Noorhan.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ – the number of test cases.

The following $$$t$$$ lines each contain an integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$.

Output

For each test case, print one integer $$$a$$$, if there are multiple answers print the smaller one.

Example
Input
7
1
2
3
4
5
6
7
Output
2
2
3
3
5
5
7