P = [1]*100001
P[0] = 0
P[1] = 0
for i in range(350):
    if P[i] == 1:
        for j in range(i*i,100001,i):
            P[j] = 0
for i in range(100000):
    P[i+1] += P[i]

T = int(input())
for t in range(T):
    N = int(input())
    print(P[N])