골드바흐의 추측

면접 대비

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

요약

주어진 짝수를 두 소수의 합으로 나타내는 모든 경우를 세어 순서대로 출력합니다.

난이도: 쉬움10점 중 3점
유형: 정수론, 완전 탐색
정답자: 아직 제출이 없습니다

문제

주어진 짝수를 두 소수의 합으로 나타내는 서로 다른 방법을 모두 찾는다. 소수는 1보다 큰 정수 중에서 1과 자기 자신으로만 나누어떨어지는 수다. 작은 것부터 적으면 2, 3, 5, 7, 11, ... 이다.

독일 수학자 골드바흐 (Christian Goldbach, 1690-1764)는 2보다 큰 모든 짝수를 두 소수의 합으로 나타낼 수 있다고 추측했다. 이 추측은 아직 증명되지도 않았고 반례도 나오지 않았다. 이 문제에서 다루는 범위에서는 추측이 참이라고 가정해도 된다.

한 짝수를 두 소수의 합으로 나타내는 방법은 여러 가지일 수 있다. 예를 들어 26은 3 + 23, 7 + 19, 13 + 13으로 나타낼 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 $n$ 이 주어진다. ( $1 \le n \le 100$ )

이어지는 $n$ 개의 줄에는 각각 짝수 $x$ 가 하나씩 주어진다. ( $4 \le x \le 32000$ )

출력

각 테스트 케이스마다 먼저 x has k representation(s) 형식으로 한 줄을 출력한다. $x$ 는 입력으로 주어진 짝수이고, $k$ 는 $x$ 를 두 소수의 합으로 나타내는 서로 다른 방법의 수다. $k$ 가 1일 때도 representation(s)를 그대로 출력한다.

그다음 각 방법을 a+b 형식으로 한 줄에 하나씩, 첫째 항 $a$ 가 증가하는 순서로 출력한다. 같은 방법이 두 번 나오지 않도록 $a$ 는 항상 $b$ 이하여야 한다.

테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제6

예제 1

입력

예상 출력

4 has 1 representation(s)
2+2

26 has 3 representation(s)
3+23
7+19
13+13

100 has 6 representation(s)
3+97
11+89
17+83
29+71
41+59
47+53

예제 2
입력
```
1
4
```
예상 출력
```
4 has 1 representation(s)
2+2
```
예제 3
입력
```
1
6
```
예상 출력
```
6 has 1 representation(s)
3+3
```

예제 4

입력

예상 출력

8 has 1 representation(s)
3+5

10 has 2 representation(s)
3+7
5+5

12 has 1 representation(s)
5+7

14 has 2 representation(s)
3+11
7+7

16 has 2 representation(s)
3+13
5+11

18 has 2 representation(s)
5+13
7+11

예제 5

입력

예상 출력

22 has 3 representation(s)
3+19
5+17
11+11

34 has 4 representation(s)
3+31
5+29
11+23
17+17

68 has 2 representation(s)
7+61
31+37

128 has 3 representation(s)
19+109
31+97
61+67

예제 6

입력

예상 출력

4 has 1 representation(s)
2+2

4 has 1 representation(s)
2+2

4 has 1 representation(s)
2+2

4 has 1 representation(s)
2+2

4 has 1 representation(s)
2+2