33472번 - 재우가 매년 다짐하는 것은 무엇일까 서브태스크스페셜 저지

문제

재우는 매년 1월 1일 떠오르는 태양을 보며 올해는 면허를 따야지 다짐한다. 무려 6년째.

그리고 재우는 올해 목표가 하나 더 있다. 바로 2022년 동우와 함께 만든 MatKor를 후배에게 넘겨주는 것. 재우는 MatKor를 후배에게 넘겨주기 전에, 그동안 MatKor가 어떻게 성장하고 발전해 왔는지 MatKor의 시작부터 회상해 보았다.

현대모비스는 일(Work)이나 커리어(Career)의 측면 뿐만 아니라 생활(Wellbeing) 측면에서도 직원들에게 많은 혜택을 주는 것으로 유명하다. 그중에서도 차량구입비 지원 및 기타 차량 복지는 회사가 현대모비스인 만큼 최고급 복지를 자랑한다. 구체적으로 임직원의 현대/기아차 구매 시 차량 할인 및 구입비를 최대 30%까지를 지원하며, 신입사원 첫 차 구매 시 20% 할인과 공임비/부품비 30% 할인을 지원한다. 구체적인 내용은 이 링크를 참고하자.

재우는 이제 대학을 졸업하여 현대모비스에 입사하기로 했다. 그러나 재우는 아직도 면허가 없다.

현대모비스의 사내 복지 혜택 중 현대/기아차 구입비 지원을 활용하고 싶던 재우는 면허는 나중에 따고, 우선 신차를 구입하고 번호판을 만들기로 했다. 재우의 번호판은 네 자리가 아닐 수 있으며, 숫자가 하나씩 적힌 숫자판을 원하는 순서대로 이어 붙여 번호판을 만든다. 재우는 숫자 $i(0\le i\le 9)$가 적혀있는 숫자판이 $a_i$개 있다.

재우는 소수가 싫기 때문에 가지고 있는 숫자를 잘 재배열하여 수가 합성수가 되게 하고 싶다. 그러나 이것이 불가능할 수 있기 때문에 재우는 다음 행동을 최대 한 번 할 수 있다. 상황에 따라 행동하지 않아도 된다.

• 1ドル\le a_i\le a_j$와 $j\ne 0$을 만족하는 서로 다른 $i$와 $j$를 한 쌍 골라, $i$가 적혀있는 숫자판 하나를 $j$로 바꾼다.

재우가 위의 행동을 한 번도 할 수 없는 상황은 주어지지 않는다고 가정하자.

재우가 가진 숫자판들의 개수 $a_i$가 주어질 때, 이를 잘 재배열해 합성수를 만들어 보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 번째 줄에 $a_0,ドル $a_1,ドル $a_2,ドル $\cdots,ドル $a_9(0\le a_i\le 10^6)$를 나타내는 10ドル$개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스 별로 재우가 행동을 한 번도 할 수 없는 상황은 주어지지 않음이 보장된다.

또한, $t$번째 테스트 케이스에 대해 $M_t=\displaystyle\max_{0\le i \le 9}{a_i}$라고 할 때, $\sum_{t=1}^{T}M_t \le 10^6$을 만족한다.

테스트 케이스의 개수는 1ドル$개 이상이며, 이 조건 하에서 테스트 케이스 개수의 상한을 구할 수 있다.

출력

각 테스트 케이스 별로 한 줄에 하나씩 아래 형식에 맞추어 출력한다.

• 만약 주어지는 수를 재배열해 합성수를 $N$을 만들 수 있다면 $N = A \times B$의 형식으로 출력한다.
  • 이때, $A,ドル $B$는 2ドル$ 이상의 정수이며, $N=A\times B$을 만족해야 한다.
  • $N$은 재우가 위의 행동을 통해 만들 수 있는 정수여야 한다.
  • 가능한 정답이 여러 가지라면 아무거나 하나 출력한다.
  • 출력하는 모든 수는 0ドル$으로 시작해서는 안 된다.
  • $\times$는 알파벳 대문자 X로 대체하여 출력한다.
  • 자세한 형식은 예제를 참고하자.
• 만약 합성수를 만들 수 없다면 대신 PRIME!을 출력한다.

제한

서브태스크

힌트