Program Pollard_Rho;
Const
  MaxN = 65535;
  MaxM = 6542;
Var
  f: Array [1..MaxN] Of Boolean;
  Prime_List: Array [1..MaxM] Of Int64;
  t: LongInt;
  n, Answer: Int64;

Procedure initialize;
Var
  i, j, p: LongInt;
Begin
  p := 0;
  For i := 2 To MaxN Do
    If Not f[i] Then
    Begin
      Inc(p); Prime_List[p] := i;
      For j := i To MaxN Div i Do f[i * j] := True;
    End;
End;

Function Modular_Multiply(a, b, n: Int64): Int64;
Var
  s: Int64;
Begin
  s := 0;
  While b <> 0 Do
  Begin
    If Odd(b) Then s := (s + a) Mod n;
    a := (a + a) Mod n; b := b Div 2;
  End;
  Exit(s);
End;

Function Modular_Exponentiation(a, b, n: Int64): Int64;
Var
  s: Int64;
Begin
  s := 1;
  While (b <> 0) And (a <> 1) Do
  Begin
    If Odd(b) Then s := Modular_Multiply(s, a, n);
    a := Modular_Multiply(a, a, n);
    b := b Div 2;
  End;
  Exit(s);
End;

Function Miller_Rabbin(n: Int64): Boolean;
Const
  Test_Number = 9;
Var
  i: LongInt;
Begin
  For i := 1 To Test_Number Do
  Begin
    If Prime_List[i] >= n Then Break;
    If Modular_Exponentiation(Prime_List[i], n - 1, n) <> 1 Then Exit(False);
  End;
  Exit(True);
End;

Function GCD(a, b: Int64): Int64;
Var
  c: Int64;
Begin
  While b <> 0 Do
  Begin
    c := a Mod b;
    a := b; b := c;
  End;
  Exit(a);
End;

Function Pollard_Rho(n: Int64): Int64;
Var
  d, x, y, k: Int64;
  i: LongInt;
Begin
  x := Random(n - 2) + 1; y := x;
  i := 1; k := 2;
  Repeat
    Inc(i);
    x := (Modular_Multiply(x, x, n) + n - 1) Mod n;
    d := GCD(Abs(y - x), n);
    If (d > 1) And (d < n) Then Exit(d);
    If i = k Then
    Begin
      y := x; k := k * 2;
    End;
  Until False;
End;

Function Min(x, y: Int64): Int64;
Begin
  If x < y
    Then Exit(x)
    Else Exit(y);
End;

Procedure Factor(n: Int64);
Var
  t, Limit: Int64;
  i: LongInt;
Begin
  If Miller_Rabbin(n) Then Exit;
  Limit := Min(Trunc(Sqrt(n)), Answer);
  For i := 1 To MaxM Do
  Begin
    If Prime_List[i] > Limit Then Break;
    If n Mod Prime_List[i] = 0 Then
    Begin
      Answer := Prime_List[i];
      Exit;
    End;
  End;
  If MaxN >= Answer Then Exit;
  t := Pollard_Rho(n);
  Answer := Min(Answer, Min(t, n Div t));
  Factor(t); Factor(n Div t);
End;

Begin
  Initialize;
  Randomize;
  Read(t);
  While t > 0 Do
  Begin
    Dec(t);
    Read(n);
    If Miller_Rabbin(n)
      Then WriteLn('Prime')
      Else Begin
             Answer := n;
             Factor(n);
             WriteLn(Answer);
           End;
  End;
End.