#!/usr/bin/env python3 import math lim = 10**6+1 factors = [[] for _ in range(lim)] for p in range(2,1000): if factors[p] != []: continue for q in range(p, lim, p): factors[q].append(1) p_pow = p**2 while p_pow < lim: for q in range(p_pow, lim, p_pow): factors[q][-1] += 1 p_pow *= p factors = [tuple(sorted(x)) for x in factors] factor_set = set(factors) # 289 elements nsol = {(): 0, (1,): 0, (2,): 0, (1, 1): 8, (3,): 0, (1, 2): 32, (4,): 8, (1, 3): 72, (1, 1, 1): 72, (5,): 24, (2, 2): 104, (1, 4): 136, (1, 1, 2): 232, (6,): 32, (2, 3): 232, (1, 5): 224, (1, 1, 3): 488, (7,): 56, (2, 4): 408, (1, 2, 2): 680, (1, 6): 320, (1, 1, 1, 1): 464, (3, 3): 480, (1, 1, 4): 848, (8,): 80, (2, 5): 648, (1, 2, 3): 1392, (1, 7): 448, (1, 1, 1, 2): 1352, (3, 4): 840, (1, 1, 5): 1312, (9,): 104, (2, 6): 920, (1, 2, 4): 2360, (1, 8): 592, (1, 1, 1, 3): 2736, (3, 5): 1312, (2, 2, 2): 1896, (1, 1, 6): 1864, (10,): 136, (1, 3, 3): 2784, (2, 7): 1264, (1, 1, 2, 2): 3760, (4, 4): 1440, (1, 2, 5): 3600, (1, 9): 752, (1, 1, 1, 4): 4624, (3, 6): 1848, (2, 2, 3): 3816, (1, 1, 7): 2528, (11,): 176, (1, 3, 4): 4688, (2, 8): 1648, (1, 1, 1, 1, 1): 2640, (1, 1, 2, 3): 7472, (4, 5): 2224, (1, 2, 6): 5080, (1, 10): 936, (1, 1, 1, 5): 7016, (3, 7): 2520, (2, 2, 4): 6384, (1, 1, 8): 3288, (12,): 208, (1, 3, 5): 7104, (2, 9): 2088, (1, 1, 1, 1, 2): 7312, (1, 1, 2, 4): 12480, (4, 6): 3128, (2, 3, 3): 7552, (1, 2, 7): 6840, (1, 11): 1144, (1, 2, 2, 2): 10184, (1, 4, 4): 7840, (1, 1, 1, 6): 9896, (3, 8): 3280, (2, 2, 5): 9664, (1, 1, 3, 3): 14696, (1, 1, 9): 4144, (5, 5): 3400, (13,): 256, (1, 3, 6): 9984, (2, 10): 2576, (1, 1, 1, 1, 3): 14480, (1, 1, 2, 5): 18800, (4, 7): 4240, (2, 3, 4): 12576, (1, 2, 8): 8848, (1, 12): 1360, (1, 2, 2, 3): 20016, (1, 4, 5): 11832, (1, 1, 1, 7): 13288, (3, 9): 4128, (1, 1, 1, 2, 2): 19760, (2, 2, 6): 13576, (1, 1, 3, 4): 24432, (1, 1, 10): 5104, (5, 6): 4776, (14,): 304, (1, 3, 7): 13400, (2, 11): 3128, (1, 1, 1, 1, 4): 24152, (1, 1, 2, 6): 26400, (4, 8): 5496, (2, 3, 5): 18936, (1, 2, 9): 11120, (1, 13): 1608, (1, 2, 2, 4): 33200, (1, 4, 6): 16600, (1, 1, 1, 8): 17176, (3, 3, 3): 14784, (3, 10): 5088, (1, 1, 1, 2, 3): 38712, (2, 2, 7): 18208, (1, 1, 1, 1, 1, 1): 14168, (1, 1, 3, 5): 36680, (1, 1, 11): 6168, (5, 7): 6440, (2, 4, 4): 20864, (15,): 352, (1, 3, 8): 17304, (2, 12): 3712, (1, 1, 1, 1, 5): 36328, (1, 2, 3, 3): 39072, (1, 5, 5): 17800, (1, 1, 2, 7): 35320, (4, 9): 6912, (2, 3, 6): 26536, (2, 2, 2, 2): 27152, (1, 1, 4, 4): 40488, (1, 2, 10): 13648, (6, 6): 6696, (1, 14): 1872, (1, 2, 2, 5): 49800, (1, 4, 7): 22232, (1, 1, 1, 9): 21560, (3, 3, 4): 24552, (3, 11): 6160, (1, 1, 1, 2, 4): 64160, (2, 2, 8): 23480, (1, 1, 1, 1, 1, 2): 38192, (1, 1, 3, 6): 51392, (1, 1, 12): 7320, (5, 8): 8328, (2, 4, 5): 31344, (16,): 408, (1, 3, 9): 21696, (1, 1, 2, 2, 2): 52624, (2, 13): 4368, (1, 1, 1, 1, 6): 50992, (1, 2, 3, 4): 64616, (1, 5, 6): 24944, (1, 1, 2, 8): 45528, (4, 10): 8496, (1, 1, 1, 3, 3): 75432, (2, 3, 7): 35496, (2, 2, 2, 3): 53008, (1, 1, 4, 5): 60664, (1, 2, 11): 16448, (6, 7): 9024, (1, 15): 2152, (1, 2, 2, 6): 69736, (1, 4, 8): 28664, (1, 1, 1, 10): 26448, (3, 3, 5): 36856, (3, 12): 7296, (1, 1, 1, 2, 5): 96120, (2, 2, 9): 29456, (1, 1, 1, 1, 1, 3): 74712, (1, 1, 3, 7): 68640, (1, 1, 13): 8584, (5, 9): 10456, (2, 4, 6): 43872, (17,): 472, (1, 3, 10): 26600, (1, 1, 2, 2, 3): 102416, (2, 14): 5064, (1, 1, 1, 1, 7): 68168, (1, 2, 3, 5): 96696, (1, 5, 7): 33352, (1, 1, 2, 9): 57040, (3, 4, 4): 40640, (4, 11): 10264, (1, 1, 1, 3, 4): 124664, (2, 3, 8): 45720, (2, 2, 2, 4): 87552, (1, 1, 1, 1, 2, 2): 101560, (1, 1, 4, 6): 84896, (1, 2, 12): 19488, (6, 8): 11664, (1, 3, 3, 3): 75912, (2, 5, 5): 46984, (1, 16): 2456, (1, 2, 2, 7): 93096, (1, 4, 9): 35912, (1, 1, 1, 11): 31840, (3, 3, 6): 51552, (3, 13): 8568, (1, 1, 1, 2, 6): 134560, (1, 2, 4, 4): 106656, (2, 2, 10): 36080, (1, 6, 6): 34920, (1, 1, 1, 1, 1, 4): 123736, (1, 1, 3, 8): 88376, (1, 1, 14): 9944, (5, 10): 12832, (2, 4, 7): 58616, (18,): 528, (2, 2, 3, 3): 102984, (1, 1, 5, 5): 90768, (1, 3, 11): 32016, (1, 1, 2, 2, 4): 169080, (7, 7): 12128, (2, 15): 5816, (1, 1, 1, 1, 8): 87840, (1, 2, 3, 6): 135216, (1, 5, 8): 42960, (1, 1, 2, 10): 69848, (3, 4, 5): 60888, (4, 12): 12152, (1, 1, 1, 3, 5): 186408, (2, 3, 9): 57256, (2, 2, 2, 5): 130992, (1, 1, 1, 1, 2, 3): 197432, (1, 1, 4, 7): 113272, (1, 2, 13): 22808, (6, 9): 14632, (1, 3, 3, 4): 125288, (2, 5, 6): 65712, (1, 17): 2784, (1, 2, 2, 8): 119800, (1, 4, 10): 43984, (1, 1, 2, 3, 3): 198632, (1, 1, 1, 12): 37720, (3, 3, 7): 68856, (3, 14): 9928, (1, 1, 1, 2, 7): 179520, (1, 2, 4, 5): 159416, (2, 2, 11): 43416, (1, 6, 7): 46664, (1, 1, 1, 1, 1, 5): 185264, (1, 1, 3, 9): 110600, (1, 2, 2, 2, 2): 138896, (1, 1, 15): 11400, (5, 11): 15472, (1, 1, 1, 4, 4): 205672, (1, 1, 1, 1, 1, 1, 1): 73752, (2, 4, 8): 75432, (19,): 600, (2, 2, 3, 4): 169776, (1, 1, 5, 6): 126928, (1, 3, 12): 37896, (1, 1, 2, 2, 5): 252680, (7, 8): 15656, (2, 16): 6616, (1, 1, 1, 1, 9): 110008, (1, 2, 3, 7): 180296, (1, 5, 9): 53784, (1, 1, 2, 11): 83968, (3, 4, 6): 85104, (4, 13): 14248, (1, 1, 1, 3, 6): 260616, (2, 3, 10): 70080, (2, 2, 2, 6): 183104, (1, 1, 1, 1, 2, 4): 325800, (1, 1, 4, 8): 145728, (1, 2, 14): 26376, (6, 10): 17952, (1, 3, 3, 5): 187200, (2, 5, 7): 87696, (1, 18): 3120, (1, 2, 2, 9): 149912, (4, 4, 4): 67112, (1, 4, 11): 52896, (1, 1, 2, 3, 4): 327336, (1, 1, 1, 13): 44112, (3, 3, 8): 88624, (3, 15): 11376, (1, 1, 1, 2, 8): 230968, (1, 1, 1, 2, 2, 2): 267824, (1, 2, 4, 6): 222752, (2, 2, 12): 51384, (1, 6, 8): 60080, (1, 1, 1, 1, 1, 6): 259280, (1, 1, 3, 10): 135336, (1, 2, 2, 2, 3): 269208, (3, 5, 5): 91080, (1, 1, 16): 12960, (5, 12): 18312, (1, 1, 1, 4, 5): 307200} answers = [nsol[tup] for tup in factors] cumans = [0]*(lim+1) for i in range(lim-1): cumans[i+1] = cumans[i] + answers[i+1] for q in range(int(input())): n = int(input()) x = int(n**(1/3)) if (x+1)**3 <= n: x += 1 if x**3 > n: x -= 1 print(cumans[x])