숫자 게임

바르첸스(Bartjens) 교수는 칠판 위에서 진행하는 2인용 암산 게임을 고안했다.

게임을 시작할 때 칠판에는 양의 정수 하나가 적혀 있다. 게임이 진행되는 동안 칠판에는 다른 양의 정수들이 더 나타날 수 있다. 두 사람은 번갈아 가며 한 번씩 두며, 자기 차례인 사람은 칠판이 비어 있지 않는 한 반드시 한 번 움직여야 한다. 칠판이 비면 게임이 끝난다. 한 번의 움직임은 다음 중 하나이다.

• 칠판에 1이 있으면 그것을 가져올 수 있다. 1점을 얻고 그 수는 지워진다.
• 칠판에 소수 $p$가 있으면 1을 뺄 수 있다. 1점을 얻고 $p$는 $p-1$로 바뀐다.
• 칠판에 합성수 $c$가 있으면, $a \cdot b = c$를 만족하며 $c$보다 작은 두 양의 정수 $a$와 $b$로 바꿀 수 있다. 이때는 점수를 얻지 못한다.

각 사람은 가능한 한 많은 점수를 모으려 한다.

이 게임에 대해 다음 두 사실이 알려져 있다.

1. 두 사람이 얻는 점수의 합은 게임을 어떻게 진행하든 항상 같다. 따라서 자신의 점수를 최대로 하는 것은 곧 상대의 점수를 최소로 하는 것과 같다.
2. 점수를 얻을 수 있을 때는 항상 얻는 것이 최선이다.

처음에 적힌 수가 주어지고 두 사람이 모두 자신의 점수를 최대로 하도록 최적으로 둔다고 할 때, 그 결과를 구하여라.

첫째 줄에 시나리오의 수를 나타내는 양의 정수 $n$이 주어진다.

이어지는 $n$개의 줄에는 각각 칠판에 처음 적히는 양의 정수 $m$ ($m < 1000000$)이 하나씩 주어진다.

각 시나리오마다 두 사람이 모두 자신의 점수를 최대로 하도록 두었을 때 각자가 얻는 점수를, 공백 하나로 구분하여 한 줄에 두 정수로 출력한다. 첫 번째 정수는 먼저 두는 사람(선공)이 얻는 점수이다.