골드바흐의 추측

면접 대비

시간 제한2초메모리 제한256 MB

요약

짝수 n이 주어지면 합이 n이 되고 차이가 가장 작은 두 소수를 출력합니다.

난이도: 쉬움10점 중 3점
유형: 정수론, 투 포인터
정답자: 아직 제출이 없습니다

문제

$1$ 보다 큰 자연수 중에서 $1$ 과 자기 자신 말고는 약수가 없는 수를 소수라고 한다. 예를 들어 $5$ 는 $1$ 과 $5$ 외에 약수가 없으므로 소수이지만, $6$ 은 $6 = 2 \times 3$ 이므로 소수가 아니다.

골드바흐의 추측은 정수론의 유명한 미해결 문제로, $2$ 보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 주장이다. 이렇게 나타낼 수 있는 수를 골드바흐 수라 하고, 짝수를 두 소수의 합으로 적은 식을 그 수의 골드바흐 파티션이라고 한다. 예를 들면 $4 = 2 + 2$ , $6 = 3 + 3$ , $8 = 3 + 5$ , $10 = 5 + 5$ , $12 = 5 + 7$ , $14 = 3 + 11 = 7 + 7$ 과 같다. $10000$ 이하의 모든 짝수는 골드바흐 파티션을 가진다.

$2$ 보다 큰 짝수 $n$ 이 주어질 때, $n$ 의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 가능한 파티션이 여러 개라면 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 각 테스트 케이스는 한 줄로 이루어지며, 짝수 $n$ 이 하나씩 주어진다.

출력

각 테스트 케이스마다 $n$ 의 골드바흐 파티션을 이루는 두 소수를 출력한다. 더 작은 소수를 먼저 쓰고, 두 수를 공백으로 구분한다.

제한

$4 \le n \le 10000$

예제4

예제 1
입력
```
3
8
10
16
```
예상 출력
```
3 5
5 5
5 11
```
예제 2
입력
```
2
4
6
```
예상 출력
```
2 2
3 3
```
예제 3
입력
```
4
4
8
32
128
```
예상 출력
```
2 2
3 5
13 19
61 67
```

예제 4

입력

예상 출력