Awesome Numbers

As everyone knows, Kipa's favorite integer is 120. It has the following properties.

• $(\zeta(-3))^{-1}$.
• It is the first triperfect number.
• It is the factorial of 5.
• It is the 10th highly composite number.
• It is the 15th triangular number.

The properties are listed in Kipa's order of preference.

Kipa also likes integer families, meaning subsets of the integers that satisfy some property. Kipa likes two families that are not on the list above: the primes and the perfect squares. So Kipa defined these operations:

• $P(n)$: the $n$th prime.
• $S(n)$: the $n$th perfect square.

For example, $5 = P(P(P(1)))$ applies $P$ three times to 1, and $7 = P(S(P(1)))$ applies $P$, then $S$, then $P$. Kipa starts from 1 and repeatedly applies $P$ or $S$. The integers reachable this way form the awesome numbers. Given a positive integer, decide whether it is an awesome number and make Kipa happy.

The first line contains the number of test cases $T$. $T$ is a positive integer at most $10^5$.

Each of the next $T$ lines contains a positive integer $n$ at most $10^{15}$.

Print $T$ lines, similar to the sample output. For those who complained about the word "similar", the conditions are written below as regular expressions.

• If $n$ is not an awesome number, print -1.
• If $n$ is an awesome number, print the shortest string $S$ that satisfies all of the following conditions.
  • The regular expression ^1( [PS] [1-9][0-9]*)*$ accepts $S$.
  • The regular expression ^.*n\$ accepts $S$.
  • For any substring $s$ that has a non-digit character immediately before and after $S$:
    • If the regular expression ^([0-9]+) P ([0-9]+)\$ accepts $s$, then P({1}) = {2}` holds.
    • If the regular expression ^([0-9]+) S ([0-9]+)\$ accepts $s$, then S({1}) = {2}` holds.

If $n$ is an awesome number, at least one string satisfying these conditions is guaranteed to exist. If several shortest $S$ exist, you may print any one of them.