include<bits/stdc++.h>

using namespace std;

define int long long

define uint unsigned long long

define ld long double

define int128 __int128

define uint128 __uint128_t

define pii pair<int,int>

define piii pair<pair<int,int>,int>

define vi vector<int>

define vpii vector<pii>

define vb vector<bool>

define PI acos(-1)

define pb push_back

define pf push_front

define ins insert

define F first

define S second

define forn(k,n) for(int i=k;i<=n;i++)

define fornr(k,n) for(int i=k;i>=n;i--)

define all(x) (x).begin(),(x).end()

define maxelement(x) *max_element(all(x))

define minelement(x) *min_element(all(x))

define lb lower_bound

define ub upper_bound

define El_Musta_7 ios_base::sync_with_stdio(0); cin.tie(); cout.tie(0);

define dbg(x) cerr<<#x<<" = "<<x<<"\n"

define raya cerr<<" ========================================= "<<"\n"

define M 1000000007

define mod(x) (((x)%M+M)%M)

define max 1000000000000000000

define min LLONG_MIN

define MAXN 200005

// *MATH*

/ const int N=10000001; int lp[N]; //menor divisor primo vi pr; //primos void criba(){ pr.push_back(2); for(int i=4;i<N;i+=2) lp[i]=2; for(int i=3;ii<N;i+=2){ if(!lp[i]){ pr.push_back(i); for(int j=0;j<N;j+=2*i) lp[i]=i; } } }

//Criba Lineal const int X=10000001; int lp[N]; vi pr; void criba(){ for(int i=2;i<N;i++) { if(!lp[i]){ lp[i]=i; pr.push_back(i); } for(int j=0;j<(int)pr.size() && pr[j]<=lp[i] && ipr[j]<N;j++) lp[ipr[j]]=pr[j]; } } */

int mul(int a,int b){ return mod((__int128)a*b); }

long long binpow(long long base, long long exp, long long MOD) { long long res = 1; base %= MOD; while (exp ) { if (exp & 1) res = ((__int128)resbase)%MOD; base = ((__int128)basebase)%MOD; exp >>= 1; } return res; }

int inv(int a){ return binpow(a,M-2,max); }

/ int inv(int a,int b){ a%=b; if(!a) return 0; int ans=(1-(__uint128_t)binv(b,a))/a; return (ans+b)%b; } */

int gcd(int a,int b){ return (!a)?b:gcd(b%a,a); }

int lcm(int a,int b){ return (a*b)/gcd(a,b); }

//*Coeficientes binomiales* vi f(MAXN);

void build(){ f[0]=1; for(int i=1;i<MAXN;i++) f[i]=mod(f[i-1]*i); }

int coe(int n,int k){ if(n<k) return 0; return mul(f[n],inv(f[n-k]*f[k])); }

//*Miller Rabin (saber si n es primo)* bool is_prime(long long n) { if (n < 2) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; if(n%6!=1 && n%6!=5) return false; // Escribir n-1 como d*2^r long long d = n - 1; int r = 0; while(!(d&1)){ d>>=1; r++; }

// Bases para test (cubre hasta 2^64)
vector<long long> bases;
if (n < 4759123141LL) bases = {2, 7, 61};
else if (n < 341550071728321LL) bases = {2, 3, 5, 7, 11, 13, 17};
else bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

for (long long a : bases) {
    if (a % n == 0) continue;
    long long x = binpow(a, d, n);
    if (x == 1 || x == n - 1) continue;

    bool composite = true;
    for (int i = 0; i < r - 1; i++) {
        x = ((__int128)x*x)%n;
        if (x == n - 1) {
            composite = false;
            break;
        }
    }
    if (composite) return false;
}
return true;

}

// Algoritmo de Pollard's Rho long long pollards_rho(long long n) { if (n % 2 == 0) return 2;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<long long> dis(2, n - 1);

long long x = dis(gen), y = x, c = dis(gen), d = 1;

auto f = [&](long long x) { return (((__int128)x*x)%n + c) % n; };

while (d == 1) {
    x = f(x);
    y = f(f(y));
    d = gcd(abs(x - y), n);

    if (d == n) {
        x = dis(gen);
        y = x;
        c = dis(gen);
        d = 1;
    }
}
return d;

}

// Función principal de factorización vector<long long> factorizar_avanzado(long long n) { vector<long long> factores;

if (n < 2) return factores;

// Factorizar pequeños factores primero
while (n % 2 == 0) {
    factores.push_back(2);
    n /= 2;
}

while (n % 3 == 0) {
    factores.push_back(3);
    n /= 3;
}

// Si el número es pequeño, usar trial division
if (n < 1000000) {
    for (long long i = 5; i * i <= n; i += (i % 6 == 1) ? 4 : 2) {
        while (n % i == 0) {
            factores.push_back(i);
            n /= i;
        }
    }
    if (n > 1) factores.push_back(n);
    return factores;
}

// Usar Pollard's Rho para números grandes
vector<long long> por_factorizar = {n};

while (!por_factorizar.empty()) {
    long long m = por_factorizar.back();
    por_factorizar.pop_back();

    if (m == 1) continue;

    if (is_prime(m)) {
        factores.push_back(m);
        continue;
    }

    long long factor = pollards_rho(m);
    por_factorizar.push_back(factor);
    por_factorizar.push_back(m / factor);
}

return factores;

}

// Versión que devuelve factores únicos con multiplicidad vector<pair<long long, int>> factorizar(long long n) { vector<long long> factores = factorizar_avanzado(n); sort(factores.begin(), factores.end());

vector<pair<long long, int>> resultado;
for (long long f : factores) {
    if (resultado.empty() || resultado.back().first != f) {
        resultado.push_back({f, 1});
    } else {
        resultado.back().second++;
    }
}

return resultado;

}

// CANTIDAD DE DIVISORES int cant_divisores(vector<pair<long long, int>> f){ int aux=1; for(size_t i=0;i<f.size();i++){ aux*=(f[i].second+1); } return aux; }

// PHI DE N int phi(vector<pair<long long, int>> f){ int aux=1; for(size_t i=0;i<f.size();i++){ aux=(uint128)binpow(f[i].first,f[i].second-1,max)(f[i].first-1)%max; } return aux; }

// SUMA DE LOS DIVISORES POSITIVOS DE N int suma_divisores(vector<pair<long long, int>> f){ int aux=1; for(size_t i=0;i<f.size();i++){ aux=((uint128)aux*((binpow(f[i].first,f[i].second+1,max)-1)/(f[i].first-1)))%max; } return aux; }

int dx[8] = {-1,0,1,0,0,-1,-1,-1}; int dy[8] = {0,1,0,-1,-1,-1,0,1};

// **MATH**

signed main(){ El_Musta_7 int cp,n; cin>>cp; while(cp--){ cin>>n; cout<<"La descomposicion en factores primos de n es: "; auto factores=factorizar(n); for(size_t i=0;i<factores.size();i++){ cout<<factores[i].first; if(factores[i].second>1){ cout<<"^"<<factores[i].second; } if(i+1<factores.size()){ cout<<" * "; } } cout<<"\nCantidad de divisores de n: "<<cant_divisores(factores); cout<<"\nPhi de n: "<<phi(factores); cout<<"\nLa suma de los divisores de n: "<<suma_divisores(factores); } return 0; }