SP30737 ADAHW - Ada and Homework
题目描述
Ada带着她的作业回家了。这个作业是这么写的：
给定一个整数 $n$ ，求所有的 $k\ \ (2\le k\le n)$ ，如果$\mathcal{gcd(n,k)} = 1$，则将 $gcd(n,k-1)$ 加入 $sum$ ，求最终的 $sum$ 。
不过 $n$ 实在是太大了，Ada没有你的帮助算不出来。你能帮助她解决这个问题吗？
输入格式
第一行一个整数 $T \le 1000$ ，表示测试数据的数量。
接下来 $T$ 行，每行一个整数 $n \le 10^{18}$ 。
输出格式
对于每一个测试数据，输出最终的 $sum$ 。
## 输入输出样例
**输入#1**:
```
11
2
5
6
7
8
10
50
100
1000
524288
945406969379503350
```
**输出#1**：
```
0
3
2
5
8
6
70
260
5400
4718592
1381966975399059833610
```