HCI '16 - Cheese

View as PDF

Submit solution

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

Authors:
Problem type

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 prime (2, 3, 5, \dots) and all values are unique.

Squeak! Also, the cheeses are all arranged in sorted order in a row from left to right. YuPenG starts 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 less than or equal to M and he can only take two pieces of cheese that are 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 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 Specification

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

Output Specification

The output should contain N lines. Each line should contain the pairs which YuPenG can choose, and 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

1 \le M \le 10^{18}

Sample Input

1
5

Sample Output

(2,3)

Explanation for Sample Output

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 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.