## 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 ≤ 10 ^{18}**, 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 |