TEAMBOOK Ро-алгоритм Полларда

#include <bits/stdc++.h>
using ld = long double;
#define long long long
#define all(x) x.begin(), x.end()
using namespace std;

long f(__int128 x, long n) {
    return (long)((x * x + 1) % n);
}

__int128 powerMod(__int128 a, long p, __int128 m) {
    a %= m;
    __int128 x = 1;
    for (; p > 0; p >>= 1) {
        if (p & 1) {
            x *= a;
            x %= m;
        }
        a *= a;
        a %= m;
    }
    return x;
}

bool isPrime(long n) {
    if (n <= 2) {
        return n == 2;
    }
    if (n % 2 == 0) {
        return false;
    }
    if (n <= 40) {
        for (int d = 2; d < n; ++d) {
            if (n % d == 0) {
                return false;
            }
        }
        return true;
    }
    long p = n - 1;
    long q = p;
    while (q % 2 == 0) {
        q /= 2;
    }
    for (long a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        __int128 e = powerMod(a, p, n);
        if (e != 1) {
            return false;
        }
        __int128 x = powerMod(a, q, n);
        vector<__int128> arr;
        while (x != e) {
            arr.push_back(x);
            x *= x;
            x %= n;
        }
        bool have_1 = false;
        bool trash  = false;
        for (auto el : arr) {
            if (el == n - 1) {
                have_1 = true;
            }
        }
        for (auto el : arr) {
            if (el != 1) {
                trash = true;
            }
        }
        if (trash && !have_1) {
            return false;
        }
    }
    return true;
}

long pollard(long n, long x0, int iter) {
    long a = x0, b = x0;
    while (iter--) {
        a = f(a, n);
        b = f(f(b, n), n);
        long d = __gcd(abs(a - b), n);
        if (1 < d && d < n) {
            return d;
        }
    }
    return n;
}

long pollard(long n) {
    if (isPrime(n)) {
        return n;
    }
    for (long d = 2, e = min(1000000LL, n); d < e; ++d) {
        if (n % d == 0) {
            return d;
        }
    }
    mt19937 rnd;
    uniform_int_distribution<long> randint(0, n - 1);
    while (1) {
        long x0 = randint(rnd);
        long d = pollard(n, x0, 100000);
        if (d != n) {
            return d;
        }
    }
    return n;
}

vector<long> divisors(long n) {
    if (n < 2) {
        return {};
    }
    vector<long> st = {n};
    vector<long> ans;
    while (st.size()) {
        n = st.back();
        st.pop_back();
        long d = pollard(n);
        if (d == n) {
            ans.push_back(d);
        } else {
            st.push_back(d);
            st.push_back(n / d);
        }
    }
    sort(all(ans));
    return ans;
}

ostream &operator<<(ostream &out, __int128 i) {
    string s;
    while (s.empty() || i) {
        s += '0' + i % 10;
        i /= 10;
    }
    reverse(all(s));
    return out << s;
}

__int128 geomPr(__int128 x, int c) {
    ++c;
    __int128 y = 1;
    while (c--) {
        y *= x;
    }
    return (y - 1) / (x - 1);
}

void solve() {
    long n;
    cin >> n;
    vector<long> d = divisors(n);
    long phi = n;
    long last = -1;
    for (long x : d) {
        if (x == last) {
            continue;
        }
        last = x;
        phi -= phi / x;
    }
    last = -1;
    long cnt = 0;
    long df = 1;
    __int128 ds = 1;
    for (long x : d) {
        if (x == last) {
            ++cnt;
        } else {
            ds *= geomPr(last, cnt);
            df *= cnt + 1;
            last = x;
            cnt = 1;
        }
    }
    ds *= geomPr(last, cnt);
    df *= cnt + 1;
    cout << phi << " " << df << " " << ds << "\n";
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}