#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

vector<int> wszystkieCzynnikiPierwsze(int x)
{
    int i = 2,e;
    vector<int> liczbyPierwsze;
    e = (int)sqrt((double)x); // nie trzeba robic floor poniewaz wystarczy rzutowanie na int-a - czesc ulamkowa zostanie zignorowana
    while (i <= e)
    {
        while (x%i == 0) // jesli x dzieli sie przez i
        {
            liczbyPierwsze.push_back(i);
            x /= i;
            e = (int)sqrt((double)x);
        }
        i++;

    }
    if (x > 1)
        liczbyPierwsze.push_back(x);

    return liczbyPierwsze;
}
///
/// \param tablica MUSI BYC POSORTOWANA BY DZIALALO DOBRZE
/// \return ZWRACA obiekt który ma w sobie 1)Liczbe pierwsza 2)Jej Wykladnik

pair<int,int> stworzObiektZWykladnikiem(vector<int> &tablica)
{
    if(!tablica.empty())
    {
        pair<int,int> obiekt;
        obiekt.first=tablica[0];
        int iloscWystapien=0;
        for (const auto &item : tablica)
        {
            if(tablica[0]==obiekt.first)
            {
                tablica.erase(tablica.begin());
                iloscWystapien++;
            } else break;
        }
        obiekt.second=iloscWystapien;
        return obiekt;
    }

}

vector<pair<int,int>> wszystkieDzielniki(vector<int> &tablicaDzielnikow)
{
    vector<pair<int,int>> dzielnikiZWykladnikiem;
    while(!tablicaDzielnikow.empty())
    {
        dzielnikiZWykladnikiem.push_back(stworzObiektZWykladnikiem(tablicaDzielnikow));
    }
    return dzielnikiZWykladnikiem;
}

ostream &operator<<(ostream &os, const pair<int,int> &d) {
    os  << d.first ;
    if(d.second!=0&&d.second!=1)
    {
        os<< "^" << d.second;
    }

    return os;
}
 ostream &operator<<(ostream &os, const vector<pair<int,int>> &d) {

if(d.empty())
    return os;
else if(d.size()==1)
{
    os<<d[0]<<endl;
    return os;
}else
{
    for (int index = 0; index < d.size()-1; ++index) {
        os<<d[index]<<"*";
    }
    os<<d[d.size()-1]<<endl;
    return os;
}

}


int main()
{

    int ilosc=0;
    vector<int> liczbyDoSprawdzenia;

    int x;
    cin>>ilosc;
    vector<vector<int>> wszystkieDzielnikiZmienna;
    for(int i=0;i<ilosc;i++)
    {
        cin>>x;
        liczbyDoSprawdzenia.push_back(x);
        wszystkieDzielnikiZmienna.push_back(wszystkieCzynnikiPierwsze(x));

    }
    vector<vector<pair<int,int>>> wynik;
    for ( auto &item : wszystkieDzielnikiZmienna)
    {
        wynik.push_back(wszystkieDzielniki(item));
    }
    for (const auto &item : wynik)
        cout<<item;


    return 0;
}