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 ≤ 10*, number for which Ada wants the answer.

^{18}

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