I'll never leave you

On his way home from school, Herman often heard the swirling song "I'll never leave you" by Alexander Losev playing from the windows of the apartments. He is so used to it that he can count by ear the number of windows from which the song is playing.

The song "I'll never leave you" always plays from the window of Herman's apartment. He has memorized that his apartment is the $k$-th apartment where the song is playing, and that $\frac{k+1}{n+k}$ is a contractible fraction for some integer $n$, and the value of $k$ is the minimum possible.

You must find out, given a given number $n$, what will be Hermann's apartment.

Input

The first line contains an integer $q(1\le q\le 100)$ — the number of test cases.

This is followed by $q$ lines, each containing one integer $n(3\le n\le 10^{12})$.

Output

The output contains $q$ lines. Each line contains a single integer $k$ — the answer to the problem.

Examples