A. Print a Pedestal (Codeforces logo?)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Given the integer nn — the number of available blocks. You must use all blocks to build a pedestal.

The pedestal consists of 33 platforms for 22-nd, 11-st and 33-rd places respectively. The platform for the 11-st place must be strictly higher than for the 22-nd place, and the platform for the 22-nd place must be strictly higher than for the 33-rd place. Also, the height of each platform must be greater than zero (that is, each platform must contain at least one block).

Example pedestal of n=11n=11 blocks: second place height equals 44 blocks, first place height equals 55 blocks, third place height equals 22 blocks.

Among all possible pedestals of nn blocks, deduce one such that the platform height for the 11-st place minimum as possible. If there are several of them, output any of them.

Input

The first line of input data contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases.

Each test case contains a single integer nn (6≤n≤1056≤n≤105) — the total number of blocks for the pedestal. All nn blocks must be used.

It is guaranteed that the sum of nn values over all test cases does not exceed 106106.

Output

For each test case, output 33 numbers h2,h1,h3h2,h1,h3 — the platform heights for 22-nd, 11-st and 33-rd places on a pedestal consisting of nn blocks (h1+h2+h3=nh1+h2+h3=n, 0<h3<h2<h10<h3<h2<h1).

Among all possible pedestals, output the one for which the value of h1h1 minimal. If there are several of them, output any of them.

Example

input

Copy

6
11
6
10
100000
7
8

output

Copy

4 5 2
2 3 1
4 5 1
33334 33335 33331
2 4 1
3 4 1

Note

In the first test case we can not get the height of the platform for the first place less than 55, because if the height of the platform for the first place is not more than 44, then we can use at most 4+3+2=94+3+2=9 blocks. And we should use 11=4+5+211=4+5+2 blocks. Therefore, the answer 4 5 2 fits.

In the second set, the only suitable answer is: 2 3 1.

解题说明：此题直接构造即可，需要让h1尽可能小。

#include"stdio.h"
#include"math.h"
 
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int i, n, x, y;
		scanf("%d", &n);
		y = (n + 2) / 3;
		y++;
		n = n - y;
		x = (n + 2) / 2;
		printf("%d %d %d\n", x, y, (n - x));
	}
	return 0;
}