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:

• \(1 \le T \le 10\)
• (20 points): \(1 \le N \le 1000\)
• (30 points): \(1 \le N \le 10^6\)
• (50 points): \(1 \le N \le 10^{12}\)