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