시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 512 MB 17 6 6 42.857%

문제

여러분도 잘 알다시피, 키파가 가장 좋아하는 정수는 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에서 시작해서 PS를 반복 적용하여 만들 수 있는 정수 n을 모아, 그 정수족을 멋진 수라고 부르기로 했습니다. 양의 정수가 주어지면, 멋진 수인지 아닌지 판단해서 키파를 멋지게 만들어 줍시다.

입력

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

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

예제 입력 1

10
6
7
3
5
9
1
2
8
4
3001

예제 출력 1

-1
1 P 2 S 4 P 7
1 P 2 P 3
1 P 2 P 3 P 5
1 P 2 P 3 S 9
1
1 P 2
-1
1 P 2 S 4
1 P 2 P 3 S 9 P 23 P 83 P 431 P 3001

출처

Contest > 키파컵 > 제1회 키파컵 A번

  • 문제를 만든 사람: kipa00