#ADAHW. Ada and Homework

    ID: 3550 远端评测题 10000ms 1536MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>number-theoryfast-prime-factorization

Ada and Homework

Ada the Ladybug came home with difficult homework. Since she is very skilled mathematician, she already deduced, how to count the answer for N. Consider all numbers K(in range 2 ≤ K ≤ N), for which it is true that gcd(N,K)==1 and add gcd(N,K-1) to sum. What is the sum?

A little bit more formally, find: ∑ gcd(K-1,N), for K ∈ [2,N] where gcd(N,K)==1

Anyway the numbers are too large, so she can't do that without your help. Can you help her?

Input

The first line contains 1 ≤ T ≤ 1000 , number of test-cases.

Each of following T lines contains 2 ≤ N ≤ 1018, number for which Ada wants the answer.

Output

For each test case, print the sum of deduced formula.

Example Input

11
2
5
6
7
8
10
50
100
1000
524288
945406969379503350

Example Output

0
3
2
5
8
6
70
260
5400
4718592
1381966975399059833610