#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> spf(1000001);

void solve(ll y){
    unordered_map<ll, ll> mp;
    while(y != 1){
        ll d = spf[y];
        mp[d]++;
        y = y / d;
    }
    for(auto it : mp){
        cout << it.first << "^" << it.second << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    for(int i = 0; i < spf.size(); i++)
        spf[i] = i;
        
    for(int p = 2; p * p < spf.size(); p++){
        if(spf[p] == p){
            for(int i = p * p; i < spf.size(); i += p){
                if(spf[i] == i) spf[i] = p;
            }
        }
    }
    
    ll n;
    cin >> n;
    vector<ll> arr(n);
    for(ll i = 0; i < n; i++){
        cin >> arr[i];
    }
    for(ll i = 0; i < n; i++)
        solve(arr[i]);
        
    return 0;
}