#include using namespace std; typedef pair pii; typedef long long ll; const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f; ll res; int n, m, cnt, w[N]; int a[9][9], c[9]; inline ll qmi(ll a, ll b, ll c) { ll res = 1; while (b) { if (b & 1) res = res * a % c; a = a * a % c; b >>= 1; } return res; } bool check(ll s, int t) { if (t == 1) return 1; if (t > 4) { for (int i = 1; ; i++) { ll g = qmi(i, t, 1e18); if (g > s) return 0; if (g == s) return 1; } } int l = 1, r = 1e6; if (t == 4) r = 1e3; else if (t == 3) r = 1e4; while (l < r) { int mid = l + r + 1 >> 1; ll g = qmi(mid, t, 1e18); if (g <= s) l = mid; else r = mid - 1; } return qmi(l, t, 1e18) == s; } int main() { int T; cin >> T; while (T--) { ll s; cin >> s; for (int i = 50; i; i--) if (check(s, i)) { printf("%d\n", i); break; } } return 0; }