import sys import math def is_perfect_power(x): if x == 1: return False max_e = int(math.log2(x)) + 1 for e in range(2, max_e + 1): a = round(x ** (1.0 / e)) if a ** e == x or (a + 1) ** e == x: return True return False def solve(): input = sys.stdin.read().split() T = int(input[0]) cases = list(map(int, input[1:T+1])) for N in cases: if N == 0: print(0) continue # Calculate perfect powers perfect_powers = set() max_e = int(math.log2(N)) + 1 if N > 1 else 0 for e in range(2, max_e + 1): a = 2 while True: val = a ** e if val > N: break if val <= N: perfect_powers.add(val) a += 1 # Primitives are numbers from 1 to N that are not in perfect_powers primitives = [] for x in range(1, N + 1): if x == 1: primitives.append(1) else: if not is_perfect_power(x): primitives.append(x) count = {} # Handle x = 1 # x=1, a=1^1, m=1*b for b=1..N → V=1^b =1 for all b count[1] = count.get(1, 0) + N # Process other primitives for x in primitives: if x == 1: continue max_k = 1 while True: xk = x ** max_k if xk > N: max_k -= 1 break max_k += 1 if max_k == 0: continue for k in range(1, max_k + 1): # x^k is the a here a = x ** k if a > N: continue # For each b in 1..N, V=x^(k*b) # Compute min and max possible k*b max_m = k * N current_m_base = k for b in range(1, N + 1): m = k * b v = x ** m count[v] = count.get(v, 0) + 1 total = sum(c * c for c in count.values()) print(total) if __name__ == "__main__": solve()