import math
maxx = 1000001
sieve = [1] * maxx
root = int(math.sqrt(maxx))
for i in range(2, root+1):
    if sieve[i] == 1:
        for j in range(2 * i, maxx, i):
            if sieve[j] == 1:
                sieve[j] = 0
                sieve[i] += 1
t = int(raw_input())
for i in range(t):
    x = int(raw_input())
    print sieve[x]