time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer?x𝑥. Your task is to find any integer?y𝑦?(1≤y<x)(1≤𝑦<𝑥)?such that?gcd(x,y)+ygcd(𝑥,𝑦)+𝑦?is maximum possible.

Note that if there is more than one?y𝑦?which satisfies the statement, you are allowed to find any.

gcd(a,b)gcd(𝑎,𝑏)?is the Greatest Common Divisor of?a𝑎?and?b𝑏. For example,?gcd(6,4)=2gcd(6,4)=2.

Input

The first line contains a single integer?t𝑡?(1≤t≤10001≤𝑡≤1000)?— the number of test cases.

Each of the following?t𝑡?lines contains a single integer?x𝑥?(2≤x≤10002≤𝑥≤1000).

Output

For each test case, output any?y𝑦?(1≤y<x1≤𝑦<𝑥), which satisfies the statement.

Example

input

Copy

7

10

7

21

100

2

1000

6

output

Copy

5
6
18
98
1
750
3

解題說明：此題是一道數學題，分析后能知道最大肯定不會超過x，可以采用貪心算法，y選擇為x-1，這樣gcd(x,y)為0，則最大值就是x-1

#include <stdio.h>int main()
{int t = 0, n = 0;scanf("%d", &t);while (t--){scanf("%d", &n);printf("%d\n", n - 1);}return 0;
}