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

hide comments
2022-06-27 19:32:22 David
First Java solution!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.