from math import *
prime = [1] * (10 ** 6 + 1 )
def sang():
    prime[0] = 0
    prime[1] = 0
    for i in range(2 , isqrt((10 ** 6 + 1 )) + 1):
        if(prime[i]):
            for j in range(i * i , (10 ** 6 + 1 ), i):
                prime[j] = 0
 
if __name__ == '__main__':
    sang()
    F = [0] * (10 ** 6 + 1 )
    F[0] = 0
    F[1] = 0
    dem = 0
    for i in range(2 , (10 ** 6 + 1 )):
        if(prime[i]):
            dem += 1
        F[i] = dem
    t = int(input())
    for i in range(t):
        x = int(input())
        print(F[x])
 

ZnJvbSBtYXRoIGltcG9ydCAqCnByaW1lID0gWzFdICogKDEwICoqIDYgKyAxICkKZGVmIHNhbmcoKToKICAgIHByaW1lWzBdID0gMAogICAgcHJpbWVbMV0gPSAwCiAgICBmb3IgaSBpbiByYW5nZSgyICwgaXNxcnQoKDEwICoqIDYgKyAxICkpICsgMSk6CiAgICAgICAgaWYocHJpbWVbaV0pOgogICAgICAgICAgICBmb3IgaiBpbiByYW5nZShpICogaSAsICgxMCAqKiA2ICsgMSApLCBpKToKICAgICAgICAgICAgICAgIHByaW1lW2pdID0gMAoKaWYgX19uYW1lX18gPT0gJ19fbWFpbl9fJzoKICAgIHNhbmcoKQogICAgRiA9IFswXSAqICgxMCAqKiA2ICsgMSApCiAgICBGWzBdID0gMAogICAgRlsxXSA9IDAKICAgIGRlbSA9IDAKICAgIGZvciBpIGluIHJhbmdlKDIgLCAoMTAgKiogNiArIDEgKSk6CiAgICAgICAgaWYocHJpbWVbaV0pOgogICAgICAgICAgICBkZW0gKz0gMQogICAgICAgIEZbaV0gPSBkZW0KICAgIHQgPSBpbnQoaW5wdXQoKSkKICAgIGZvciBpIGluIHJhbmdlKHQpOgogICAgICAgIHggPSBpbnQoaW5wdXQoKSkKICAgICAgICBwcmludChGW3hdKQo=

NQozOQo2OAoyNgo4Nwo2Cg==

5
39
68
26
87
6