Submit solution

Points: 5 (partial)
Time limit: 3.0s
Memory limit: 32M

Authors:
Problem type
Allowed languages
C, C++

Lately, YuPenG the Penguin has been playing too much mousehunt during class and even got to the rank of grand duke. At one point, the magical sun, moon and star transform YuPenG from a Penguin to a mouse! Squeak! Oh no! Now, to satisfy his intense hunger for cheese, YuPenG has to eat two pieces of cheese a day. Squeak! He then caught a whiff of the smell of cheese coming from Damian's camp. Squeak! He sneaked into Damian's camp to find a row of pieces of cheese. Squeak! Each of these cheeses has a tasty value of P_i coincidentally, as Damian loves math so much, all values of P_i are all of the primes (2, 3, 5, \ldots) and all values are unique.

Squeak! Also, the cheeses are all arranged in a sorted order in the row from left to right. YuPenG starts off at the far left of the row. Squeak! However, being the lazy mouse that he is, he can only run up to the jth cheese where P_j is lesser than or equal to M and he can only take two pieces of cheese that adjacent to each other. Squeak! Also, being the math god, he will only eat the two-adjacent cheese if the sum of their values, P_i + P_{i+1} cannot be expressed as abc where a, b, c > 1. Squeak! Having so many different choices of cheeses to choose from, YuPenG is wondering exactly how many and what are the pairs take he can take for some M. Squeak! Since, YuPenG wishes to give some chance and allow others to do the math for him, he asked you to help him find the options that he has for N different queries of M. Squeak!


Input Format

The first line of input will contain one integer, N. The next N lines will each contain one line representing M.

Output Format

The output should contain N lines. Each lines should contains the pairs which YuPenG can choose, the pairs should be in the format of (P_i, P_{i+1}) with spaces between pairs. If no valid pair exists, output -1.

Constraints

1 \le N \le 1\,000\,000

Sample

Input
1
5
Output
(2,3)

Explanation
YuPenG can only move to the cheese which has a value less than or equal to 5 so he can only move to cheeses 2, 3 and 5 and the only 2 pairs are (2,3) and (3,5). 2+3=5 and cannot be expressed as any abc so YuPenG can eat this pair. However, 3+5=8 can be expressed as 8 = 2 \times 2 \times 2, thus YuPenG will not eat this pair.

Important Note

IF you're using cin/cout, increase I/O speed by placing the following code at the start of your main function:

ios_base::sync_with_stdio(false);
cin.tie(0);

Comments

There are no comments at the moment.