A = 10**7
sieve = [i for i in range(A+1)]
p = 2
while p*p <= A:
    if sieve[p] == p:
        for q in range(2*p, A+1, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

dp = [0]*(A+1)
for i in range(2, A+1):
    prime = set()
    orig = i
    while i > 1:
        prime.add(sieve[i])
        i //= sieve[i]

    res = 0
    prime = list(prime)
    l = len(prime)
    for bit in range(1, 1 << l):
        tmp = 1
        c = 1
        for j in range(l):
            if (bit >> j) & 1:
                tmp *= prime[j]
                c = (c+1) % 2
        res += orig//(tmp*(-1)**c)
    res -= 1

    dp[orig] = dp[orig-1]+orig-1+res

t = int(input())
for _ in range(t):
    n = int(input())
    print(dp[n])