SOLVE
LATER
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 \le a \le N\), \(1 \le b \le 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)\).