Question
Maximize the Expression
You are given an integer 𝑥. Your task is to find any integer y (1≤𝑦<𝑥) such that gcd(𝑥,𝑦) + 𝑦 is maximum possible.
Note that if there is more than one 𝑦 which satisfies the statement, you have to print the minimum value of y.
Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases.
Each of the following t lines contains a single integer x (2≤x≤1000).
Each of the following t lines contains a single integer x (2≤x≤1000).
Output
Print integer y, which satisfies the statement.
Example
Input:
2
10
7
Output:
5
6
Input:
5
21
100
2
1000
6
Output:
14
50
1
500
3
2
10
7
Output:
5
6
Input:
5
21
100
2
1000
6
Output:
14
50
1
500
3