Source

This problem is adapted from Long Long OJ. All rights reserved.

Problem Description

Given a number $n$, find a positive integer $m$ greater than $\bm 1$ such that $n + m$ is minimized while $\gcd(n, m) = 1$.

Why greater than $1$? Because $\gcd(x, 1) = 1$, as everyone knows.

Input Format

There are multiple test cases.

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

Each of the next $T$ lines contains a positive integer $n$.

Output Format

Output $T$ lines, each containing a positive integer $m$.

Samples

3
1
5
12

2
2
5

1
114514

3

Data Range

For $100\%$ of the data, $1 \le T \le 10^3$, $1 \le n \le 10^6$.