SP30737 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 ), 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?

The first line contains **1 , number of test-cases.** Each of following **T** lines contains **2 , number for which ada wants the answer.**

For each test case, print the sum of deduced formula.