救救孩子吧 UwU

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
const int SSQ = 31650; 
bool h[N];
vector<int> p;
void sieve() {
	for (int i = 2; i <= SSQ; i++) {
		if (!h[i]) {
			p.push_back(i);
			for (int j = 2 * i; j <= SSQ; j += i) {
				h[j] = true;
			}
		}
	}
}
int n;
LL p3[N];
int main() {
	sieve();
	for (int i = 1; i <= 1e6; i++) {
		p3[i] = 1ll * i * i * i;
	}
	scanf("%d", &n);
	LL x;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &x);
		LL ans = 1;
		for (int i = 0; i < p.size() && p[i] <= x; i++) {
			LL cnt = 0;
			while (x % p[i] == 0 && x >= p[i]) {
				cnt++;
				x /= (1ll * p[i]);
				if (cnt % 3 == 0) {
					ans *= (1ll * p[i]);
				}
			}
		}
		LL ans2 = 1, l = 1, r = 1e6;
		while (l <= r) {
			LL mid = l + r + 1 >> 1;
			if (p3[mid] >= x) {
				ans2 = mid;
				l = mid + 1;
			} else if (p3[mid] < x) {
				r = mid - 1;
			}
		}
		if (ans2 * ans2 * ans2 != x) {
			ans2 = 1;
		}
		printf("%lld\n", 1ll * ans * ans2);
	}
	return 0;
}