16640번 - Awesome Numbers

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

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

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

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

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

예를 들어, 5 = P(P(P(1)))는 1번째 소수번째 소수번째 소수이고, 7 = P(S(P(1)))은 1번째 소수번째 제곱수번째 소수입니다. 키파는 1에서 시작해서 P나 S를 반복 적용하여 만들 수 있는 정수 n을 모아, 그 정수족을 멋진 수라고 부르기로 했습니다. 양의 정수가 주어지면, 멋진 수인지 아닌지 판단해서 키파를 멋지게 만들어 줍시다.

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

둘째 줄부터 T개의 줄마다 10¹⁵ 이하의 양의 정수 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가 여러 개라면, 아무 거나 하나 출력해도 됩니다.