Quad#11854
Sign in

Quad

1 second
256 megabytes
Easy

Given an integer (1 \le n \le 10^9), find any four integers a, b, c, d such that:

\begin{cases} a + b + c + d = n \\ a, b, c, d \text{ are pairwise distinct integers} \\ a, b, c, d \text{ are not multiples of } 4 \\ 1 \le a, b, c, d \le n \end{cases}

Input

The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.

Each test case consists of a single line containing an integer (1 \le n \le 10^9).

Output

If such (a, b, c, d) exist, output them; otherwise, output .

Examples

Example 1

Loading
Loading

Note

For the first test case: no solution exists.

For the second test case: (1, 2, 3, 6) works, because all of them are distinct and none of them is a multiple of .

Scoring

  1. ( points): 1 \le n \le 15

  2. ( points): 1 \le n \le 30

  3. ( points): 1 \le \sum n \le 100

  4. ( points): 1 \le \sum n \le 1000

  5. ( points): 1 \le \sum n \le 10^6

  6. ( points): No additional constraints.