Question

Maximize the Expression

2

10

7

5

6

5

21

100

2

1000

6

14

50

1

500

3

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