题目详情 - 欧几里得 - 南阳理工学院OJ

ID: 1083

远端评测题

1000ms

128MiB

难度: (无)

上传者:

已知gcd(a,b)表示a,b的最大公约数。<o:p></o:p>

现在给你一个整数n，你的任务是在区间[1,n)里面找到一个最大的x，使得gcd(x,n)等于1。

Input

输入文件的第一行是一个正整数T，表示有T组测试数据
接下来有T行，每行有一个正整数n (1<=n<=10^1000)。

Output

每组测试输出要求x。

Sample Input

2
4
7

Sample Output

3
6

HINT

Source