import std.stdio, std.algorithm, std.array, std.conv, std.typecons;

immutable Nmax = 10L^^12;

auto dictionary() {
	bool[ulong][] powers;
	powers.length = 40;
	foreach (n; 3 .. 31) {
		auto a = 2L;
		while (a^^n <= Nmax) {
			powers[n][a^^n] = true;
			a++;
		}
	}
	foreach (n; 31 .. 40) {
		powers[n][2L^^n] = true;
	}
	
	ulong[ulong] result;
	foreach (n, aarray; powers)
		foreach (key, _; aarray)
			result[key] = n;
	return result;
}

bool is_square(ulong N) {
	import std.math;
	auto root = cast(ulong) (cast(double) N).sqrt;
	return root^^2 == N;
}

ulong solve(ulong N, ulong[ulong] dict) {
	if (auto ptr = N in dict)
		return *ptr;
	else if (is_square(N))
		return 2;
	else
		return 1;
}


void main() {
	auto Q = readln[0 .. $-1].to!ulong;
	ulong[] N;
	foreach (q; 0 .. Q) N ~= readln[0 .. $-1].to!ulong;
	
	auto dict = dictionary();
	foreach (n; N) solve(n, dict).writeln;
}