#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))

typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

void ssolve() {
    for(int i = 1; i <= 5000; i++) {
        vector<pii> ve;
        for(int x = 0; x * x <= i; x++) {
            int y = round(sqrt(i - x * x));
            if(x * x + y * y == i) ve.pb(Mp(x, y));
        }
        if(SZ(ve) == 0) continue;
        pii M = ve[0];
        if(ve[0].fi == 0 || ve[0].se == 0) {
            M.fi = M.se = ve[0].fi + ve[0].se;
        } else {
            M.fi = M.fi * 2, M.se = M.se * 2;
        }
        auto norm = [&](int &a, int b) {
            if(b == 0) a = 0;
            else a = ((a % b) + b) % b;
        };
        auto add = [&](pii a, pii b) {
            a.fi += b.fi, a.se += b.se;
            norm(a.fi, M.fi), norm(a.se, M.se);
            return a;
        };
        vi fa((M.fi + 1) * (M.se + 1));
        iota(fa.begin(), fa.end(), 0);
        function<int(int)> find = [&](int x) {
            return fa[x] == x ? x : fa[x] = find(fa[x]);
        };
        auto merge = [&](int x, int y) {
            x = find(x), y = find(y);
            if(x > y) swap(x, y);
            fa[y] = x;
        };
        for(auto [x, y] : ve) {
            for(int i = 0; i < M.fi; i++) {
                for(int j = 0; j < M.se; j++) {
                    auto [ti, tj] = add(Mp(i, j), Mp(x, y));
                    merge(i * (M.se) + j, ti * (M.se) + tj);
                }
            }
        }
        int cnt = 0; vi ans;
        for(int i = 0; i < (M.fi) * (M.se); i++)
            if(find(i) == i) cnt++, ans.pb(i);
        int yg = 0;
        set<int> st;
        for(auto [x, y] : ve) {
            // cout << "(" << x << ',' << y << ") ";
            st.insert(x&-x), st.insert(y&-y);
            yg = __gcd(yg, y);
        }
        // cout << ' ';
        int eig = cnt / yg / yg;
        if(eig == 2) {
            assert(SZ(st) == 1);
            cout << i << ' ';
            for(auto [x, y] : ve) {
                cout << "(" << x << ',' << y << ") ";
            }
            cout << '\n';
        } else {
            assert(SZ(st) != 1);
        }
        // cout << i << ' ' << eig << '\n';
        // cout << '\n';
        int xmx = 0, ymx = 0;
        for(auto i : ans) {
            xmx = max(xmx, i / M.se);
            ymx = max(ymx, i % M.se);
            // cout << i / (M.se) << ' ' << i % (M.se) << " | ";
        }
        // cout << '\n' << xmx + 1 << ' ' << ymx + 1 << ' ' << yg;
        assert(cnt == (xmx + 1) * (ymx + 1));
        // cout << "\n";
    }
}
void solve() {
    int R;
    cin >> R;
    set<int> st;
    int g = 0, fl = 0;
    for(int i = 0; i * i <= R; i++) {
        int j = round(R - i * i);
        if(i * i + j * j != R) continue;
        fl = 1;
        st.insert(i & -i);
        st.insert(j & -j);
        g = __gcd(g, i);
        g = __gcd(g, j);
    }
    if(fl == 0) {
        cout << "inf\n";
    } else if(SZ(st) == 1) {
        cout << 2ll * g * g << '\n';
    } else {
        cout << 1ll * g * g << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
}