const
  MaxN = 200010;
  MaxNum = 200000;

var
  n, num, p, exp, i : longint;
  a : array[0..MaxN] of longint;
  leastDiv : array[0..MaxNum + 10] of longint;
  prime : array[0..MaxNum + 10] of boolean;


procedure eratosten(N : longint);
var
  i, j : longint;

begin

  for i := 0 to N do
      prime[i] := true;

  for i := 2 to N do
      if (prime[i]) then begin
          leastDiv[i] := i;
          for j := 2 to N div i do
              if (prime[i * j]) then begin
                  prime[i * j] := false;
                  leastDiv[i * j] := i;
              end;
      end;

end;


begin

  readln(n);
  for i := 1 to n do
      readln(a[i]);

  eratosten(MaxNum);

  for i := 1 to n do begin

      num := a[i];
      while (num > 1) do begin
          p := leastDiv[num];
          exp := 0;
          while (num mod p = 0) do begin
              exp := exp + 1;
              num := num div p;
          end;

          if (num > 1) then write(p, '^', exp, '*')
          else writeln(p, '^', exp);
      end;

  end;

end.