EIU Programming Practices and Exams

Số nguyên tố là các số chỉ có thể chia hết cho 1 hoặc cho chính nó mà không thể chia hết cho số khác, ngoại trừ số 1. Ví dụ 2, 3, 5, 7, 11, … là các số nguyên tố.

Tú rất thích áp dụng xác suất thống kê lên các con số nguyên tố này và luôn muốn tìm xem, với một con số bất kì thì có bao nhiêu cách cộng 2 số nguyên tố để tạo ra con số đó.

Ví dụ số 26 có thể từ 3 + 23, 7 + 19, hoặc 13 + 13.

Input

Dòng đầu tiên là số nguyên T, số bộ dữ liệu (1 <= T <= 100).

T dòng tiếp theo là T số nguyên dương N (4 <= N <= 32000).

Output

Với mỗi bộ dữ liệu, in ra số cách có thể tạo ra số đã cho với 2 số nguyên tố. Sau đó liệt kê các cách cộng đó ra theo thứ tự tăng dần của phần tử đầu tiên của phép cộng. Phần tử đầu tiên của phép cộng phải luôn bé hơn hoặc bằng phần tử thứ 2 để tránh có 2 phép cộng giống nhau. Mỗi bộ dữ liệu phải được cách nhau ra bởi 1 dòng trống.

Example

Input:
3
4
26
100

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