max_ = 10 ** 5
isprime = [True] * (max_ + 1)
isprime[0] = isprime[1] = False
for i in range(2, int(max_ ** 0.5 + 1)):
    if not isprime[i]:
        continue
    for j in range(i * i, max_ + 1, i):
        isprime[j] = False
        
ans = [0] * (max_ + 1)
for i in range(1, max_ + 1):
    ans[i] = ans[i - 1] + isprime[i]
    
for _ in range(int(input())):
    print(ans[int(input())])