from collections import Counter

"""
Given a prime number X, you need to give the count of all numbers
 in range 1 to 106 inclusive which have minimum prime factor X.
"""

def seq_sieve(n):
	F = [0]*(n + 1)
	i = 2

	while i*i <= n:
		if F[i] == 0:	
			k = i*i

		while k <= n:
			if F[k] == 0:
				F[k] = i;

			k += i
		i += 1

	return F

def main():
	L=Counter({2: 499999, 3: 166666, 0: 78500, 5: 66666, 7: 38094, 11: 20778, 13: 15983,
	 17: 11283, 19: 9502, 23: 7434, 29: 5646, 31: 5098, 37: 4136, 41: 3617, 43: 3356,
	  47: 2982, 53: 2575, 59: 2261, 61: 2143, 67: 1910, 71: 1775, 73: 1700, 79: 1553,
	   83: 1460, 89: 1354, 97: 1244, 101: 1195, 103: 1171, 107: 1130, 109: 1109, 113: 1074,
	    127: 964, 131: 937, 137: 898, 139: 886, 149: 832, 151: 820, 157: 794, 163: 763, 167: 745, 
	    173: 719, 179: 697, 181: 689, 191: 654, 193: 647, 197: 633, 199: 629, 211: 593, 223: 562,
	     227: 551, 229: 547, 233: 539, 239: 523, 241: 518, 251: 496, 257: 485, 263: 473, 269: 462,
	      271: 457, 277: 446, 281: 439, 283: 434, 293: 418, 307: 398, 311: 391, 313: 388, 317: 381,
	       331: 367, 337: 360, 347: 349, 349: 347, 353: 340, 359: 333, 367: 325, 373: 315, 379: 308,
	        383: 304, 389: 299, 397: 291, 401: 289, 409: 283, 419: 274, 421: 270, 431: 262, 433: 260,
	         439: 254, 443: 250, 449: 245, 457: 240, 461: 238, 463: 236, 467: 233, 479: 224, 487: 218,
	          491: 215, 499: 210, 503: 205, 509: 201, 521: 196, 523: 194, 541: 184, 547: 181, 557: 177, 
	          563: 172, 569: 170, 571: 168, 577: 165, 587: 160, 593: 156, 599: 155, 601: 152, 607: 149, 
	          613: 147, 617: 144, 619: 142, 631: 136, 641: 131, 643: 129, 647: 126, 653: 124, 659: 121, 
	          661: 120, 673: 114, 677: 111, 683: 109, 691: 105, 701: 99, 709: 97, 719: 94, 727: 92, 733: 89,
	           739: 87, 743: 86, 751: 85, 757: 83, 761: 80, 769: 76, 773: 74, 787: 68, 797: 66, 809: 63,
	            811: 62, 821: 58, 823: 56, 827: 54, 829: 53, 839: 50, 853: 47, 857: 45, 859: 44, 863: 42,
	             877: 39, 881: 38, 883: 37, 887: 35, 907: 30, 911: 29, 919: 25, 929: 23, 937: 21, 941: 19, 
	             947: 17, 953: 15, 967: 12, 971: 9, 977: 8, 983: 5, 991: 3, 997: 1})
	for testcases in xrange(input()):
		print L[input()]+1

if __name__ == '__main__':
	main()