f = []
def populate_array():
    f = [0]*1000001
    c = [0]*1000001
    ctr = 0
    for i in range(2,1000001,2):
        f[i] = 2
        ctr += 1
    c[2] = ctr
    #print ctr
    for i in range(3,1000001,2):
        if f[i] == 0 :
            ctr = 0
            for j in range(i,1000001,i):
                if f[j] == 0:
                    f[j] = i
                    ctr += 1
            c[i] = ctr
    return c


t = int(raw_input())
primes = populate_array()
while t>0:
    n = int(raw_input())
    print primes[n]
    t -= 1