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.

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