I'll never leave you#11534
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 -th apartment where the song is playing, and that \frac{k+1}{n+k} is a reducible fraction for some integer , and the value of is the minimum possible.
You must find out, given a number , what will be Herman's apartment.
The first line contains an integer q~(1 \leq q \leq 100) — the number of test cases.
This is followed by lines, each containing one integer n~(3 \leq n \leq 10^{12}).
The output contains lines. Each line contains a single integer — the answer to the problem.
Example 1