ADAHW - 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
Added by: | Morass |
Date: | 2017-02-10 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |