Ada and Homework

Statement

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
	
Time and memory limit:

  • 6 seconds
  • 256MB

Problem source: SPOJ