Kevin recently learned a new algorithm called Greatest Common Divisor. He tried to implement it but he failed. He called this new algorithm Kevin's Greatest Common Divisor (KGCD). You can look at this implementation:
long long kgcd(long long a, long long b)
{
while (a > 0 && b > 0)
{
a -= b;
swap(a , b);
}
return a + b;
}
Now Kevin runs kgcd(a,b) for all 1≤a≤N, 1≤b≤N. He is interested in how many times his algorithm returns the correct gcd value of a and b.
Input format:
The first line of input will contain an integer T, denoting the number of test cases.
Each of the next T lines contain one integer N.
Output format:
For every test case output the number of times kgcd(a,b)==gcd(a,b).
Constraints:
In the first case kgcd works correct for all a,b except (2,3) and (3,4).