M. ZP
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Airplane-airplane-airplane-airplane-airplane. How can I write the problem statement about you? How can I fit you into a problem where there are no airplanes in sight? Airplane-airplane-airplane.

It is not difficult to understand that any airplane can be represented as a triple of numbers $$$(a,b,c)$$$. We will say that the airplane satisfies the quality certificate $$$p$$$ if the following conditions are met:

  • $$$0 \le a, b, c \lt p$$$ and the numbers $$$a$$$, $$$b$$$, $$$c$$$ are pairwise distinct;
  • $$$a b c - 1$$$ and $$$a + b + c$$$ are divisible by $$$p$$$.

For a prime number $$$p$$$, you need to find any triple of numbers $$$(a, b, c)$$$ that satisfies the quality certificate $$$p$$$, or state that such a triple does not exist.

Input

The first line contains the number $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each test case is described by a single line containing a single integer prime number $$$p$$$ ($$$3 \le p \le 10^9$$$).

Output

For each test case, output either a suitable triple $$$(a, b, c)$$$ or $$$-1$$$ if such a triple does not exist.

Example
Input
9
3
7
11
13
223
3967
16127
1046527
16769023
Output
-1
4 2 1
8 4 10
3 1 9
140 16 67
228 3303 436
228 6453 9446
12228 402737 631562
2045228 1664119 13059676