멋진 수

여러분도 잘 알다시피, 키파가 가장 좋아하는 정수는 120입니다. 120에는 다음과 같은 성질이 있습니다.

• $(\zeta(-3))^{-1}$입니다.
• 첫 번째 triperfect number입니다.
• 정수 5의 factorial입니다.
• 10번째 highly composite number입니다.
• 15번째 삼각수입니다.

순서는 당연히 키파가 좋아하는 성질의 순서입니다.

그러나 키파는 정수족, 즉 어떤 성질을 만족하는 정수의 부분집합도 좋아합니다. 특히 위 성질에 속하지 않는 두 정수족을 좋아하는데, 바로 소수와 제곱수입니다. 그래서 다음 연산을 생각했습니다.

• $P(n)$: $n$번째 소수입니다.
• $S(n)$: $n$번째 제곱수입니다.

예를 들어 $5 = P(P(P(1)))$은 1에 $P$를 세 번 적용한 값이고, $7 = P(S(P(1)))$은 $P$, $S$, $P$를 차례로 적용한 값입니다. 키파는 1에서 시작해서 $P$나 $S$를 반복 적용합니다. 이렇게 만들 수 있는 정수를 모아, 그 정수족을 멋진 수라고 부르기로 했습니다. 양의 정수가 주어지면 멋진 수인지 판단해서 키파를 멋지게 만들어 줍시다.

첫째 줄에 테스트 케이스의 수 $T$가 주어집니다. $T$는 $10^5$ 이하의 양의 정수입니다.

둘째 줄부터 $T$개의 줄마다 $10^{15}$ 이하의 양의 정수 $n$이 주어집니다.

$T$개의 줄에 예제 출력과 비슷하게 출력합니다. "비슷하게"라는 말에 불평을 가지고 계신 분들을 위해, 조건을 정규식으로 아래에 적어 둡니다.

• $n$이 멋진 수가 아니라면, -1을 출력합니다.
• $n$이 멋진 수라면, 다음 조건을 모두 만족하는 가장 짧은 문자열 $S$를 출력합니다.
  • 정규식 ^1( [PS] [1-9][0-9]*)*$이 $S$를 받아들입니다.
  • 정규식 ^.*n\$이 $S$를 받아들입니다.
  • $S$의 바로 앞 글자와 뒤 글자가 숫자가 아닌 임의의 부분문자열 $s$에 대하여,
    • 정규식 ^([0-9]+) P ([0-9]+)\$이 $s$를 받아들인다면, P({1}) = {2}`를 만족합니다.
    • 정규식 ^([0-9]+) S ([0-9]+)\$이 $s$를 받아들인다면, S({1}) = {2}`를 만족합니다.

$n$이 멋진 수라면, 조건을 만족하는 문자열이 하나 이상 존재함이 보장됩니다. 그러한 가장 짧은 $S$가 여러 개라면 아무 것이나 하나 출력해도 됩니다.