Goldbach's Conjecture

Interview

Time limit2sMemory limit256 MB

Summary

Count and list every pair of primes that sums to each given even number up to 32000.

Level: Easy3 of 10
Topics: Number theory, Brute force
Solved: No attempts yet

Problem

Find every distinct way to write a given even number as a sum of two primes. A prime is an integer greater than 1 that is divisible only by 1 and by itself. The smallest primes are 2, 3, 5, 7, 11, and so on.

The German mathematician Goldbach (Christian Goldbach, 1690-1764) conjectured that every even number greater than 2 can be written as a sum of two primes. Nobody has proved the conjecture and nobody has found a counterexample. You may assume it holds for every number this problem asks about.

One even number can have several such representations. For example, 26 is 3 + 23, 7 + 19, and 13 + 13.

Input

The first line has an integer $n$ , the number of test cases. ( $1 \le n \le 100$ )

Each of the next $n$ lines has one even number $x$ . ( $4 \le x \le 32000$ )

Output

For each test case, first print one line in the form x has k representation(s), where $x$ is the given even number and $k$ is the number of distinct ways to write $x$ as a sum of two primes. Print representation(s) exactly like that even when $k$ is 1.

Then print each representation on its own line in the form a+b, in increasing order of the first addend $a$ . The first addend must always be less than or equal to the second, so no representation appears twice.

Print a blank line between consecutive test cases.

Examples6

Example 1

Input

Expected output

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

Example 2
Input
```
1
4
```
Expected output
```
4 has 1 representation(s)
2+2
```
Example 3
Input
```
1
6
```
Expected output
```
6 has 1 representation(s)
3+3
```

Example 4

Input

Expected output

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

Example 5

Input

Expected output

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

Example 6

Input

Expected output

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