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)$$.