answers = {2: 500000, 3: 166667, 5: 66667, 7: 38095, 521: 197, 11: 20779, 13: 15984, 17: 11284, 19: 9503, 23: 7435, 29: 5647, 31: 5099, 547: 182, 37: 4137, 41: 3618, 43: 3357, 557: 178, 47: 2983, 563: 173, 53: 2576, 569: 171, 59: 2262, 769: 77, 61: 2144, 577: 166, 67: 1911, 991: 4, 71: 1776, 73: 1701, 587: 161, 79: 1554, 593: 157, 83: 1461, 599: 156, 89: 1355, 607: 150, 97: 1245, 101: 1196, 103: 1172, 617: 145, 107: 1131, 109: 1110, 113: 1075, 787: 69, 631: 137, 127: 965, 641: 132, 131: 938, 601: 153, 647: 127, 137: 899, 139: 887, 653: 125, 823: 57, 659: 122, 149: 833, 151: 821, 157: 795, 709: 98, 673: 115, 163: 764, 677: 112, 167: 746, 683: 110, 173: 720, 541: 185, 179: 698, 181: 690, 701: 100, 191: 655, 193: 648, 197: 634, 199: 630, 859: 45, 719: 95, 211: 594, 727: 93, 733: 90, 223: 563, 227: 552, 229: 548, 743: 87, 233: 540, 239: 524, 241: 519, 757: 84, 761: 81, 251: 497, 257: 486, 773: 75, 263: 474, 269: 463, 271: 458, 643: 130, 277: 447, 281: 440, 283: 435, 797: 67, 293: 419, 809: 64, 811: 63, 619: 143, 307: 399, 821: 59, 311: 392, 313: 389, 827: 55, 317: 382, 829: 54, 839: 51, 331: 368, 337: 361, 739: 88, 853: 48, 857: 46, 347: 350, 349: 348, 863: 43, 523: 195, 353: 341, 571: 169, 359: 334, 691: 106, 877: 40, 367: 326, 881: 39, 883: 38, 373: 316, 887: 36, 379: 309, 383: 305, 389: 300, 907: 31, 397: 292, 911: 30, 661: 121, 401: 290, 919: 26, 409: 284, 751: 86, 929: 24, 419: 275, 421: 271, 937: 22, 941: 20, 431: 263, 433: 261, 947: 18, 439: 255, 953: 16, 443: 251, 449: 246, 967: 13, 457: 241, 971: 10, 461: 239, 463: 237, 977: 9, 467: 234, 983: 6, 479: 225, 997: 2, 487: 219, 491: 216, 613: 148, 499: 211, 503: 206, 509: 202}
t=input()
for i in range(t):
    prime = input()
    if prime in answers:
        print answers[prime]
    else:
        print 1