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

The pedestal consists of $3$ platforms for $2$-nd, $1$-st and $3$-rd places respectively. The platform for the $1$-st place must be strictly higher than for the $2$-nd place, and the platform for the $2$-nd place must be strictly higher than for the $3$-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=11$ blocks: second place height equals $4$ blocks, first place height equals $5$ blocks, third place height equals $2$ blocks.

Among all possible pedestals of $n$ blocks, deduce one such that the platform height for the $1$-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 $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case contains a single integer $n$ ($6 \le n \le 10^5$) — the total number of blocks for the pedestal. All $n$ blocks must be used.

It is guaranteed that the sum of $n$ values over all test cases does not exceed $10^6$.


-----Output-----

For each test case, output $3$ numbers $h_2, h_1, h_3$ — the platform heights for $2$-nd, $1$-st and $3$-rd places on a pedestal consisting of $n$ blocks ($h_1+h_2+h_3=n$, $0 < h_3 < h_2 < h_1$).

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


-----Examples-----

Input
6
11
6
10
100000
7
8
Output
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 $5$, because if the height of the platform for the first place is not more than $4$, then we can use at most $4 + 3 + 2 = 9$ blocks. And we should use $11 = 4 + 5 + 2$ blocks. Therefore, the answer 4 5 2 fits.

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

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms


Solutions:
def pedestal(n):
	place_2 = n // 3
	remain = n % 3
	if remain:
		place_2 += 1
		remain = 3 - remain
	place_1 = place_2 + 1
	place_3 = place_2 - remain - 1
	if place_3 < 1:
		make_over = 1 - place_3
		place_3 += make_over
		place_2 -= make_over
	return (place_2, place_1, place_3)
output = []
for _ in range(int(input())):
	n = int(input())
	output.append(pedestal(n))
for _ in output:
	print(*_)


def tower():
	boxes = int(input())
	rest = boxes % 3
	towers = []
	if rest == 0:
		towers = [boxes // 3, boxes // 3 + 1, boxes // 3 - 1]
	elif rest == 2:
		towers = [boxes // 3 + 1, boxes // 3 + 2, boxes // 3 - 1]
	else:
		towers = [boxes // 3 + 1, boxes // 3 + 2, boxes // 3 - 2]
	if towers[2] == 0:
		towers[2] += 1
		towers[0] -= 1
	return towers
all = []
for i in range(int(input())):
	all.append(tower())
for tow in all:
	print(*tow)


from math import *
t = int(input())
lst = []
for i in range(t):
	lst.append(int(input()))
for q in lst:
	if q > 13 or q % 2 == 0:
		col2 = ceil((q - q // 3) / 2)
		col1 = col2 + 1
		col3 = q - col1 - col2
		print(col2, col1, col3)
	elif q == 7:
		print(2, 4, 1)
	else:
		col2 = q // 2 - q % (q // 2)
		col1 = q // 2
		print(col2, col1, q - col2 - col1)


n = int(input())
l = []
for i in range(n):
	a = int(input())
	l.append(a)
for j in l:
	x = j // 3 + 1
	y = (j - x) // 2 + 1
	if x == y:
		x = x + 1
	z = j - x - y
	if z <= 0:
		z = 1
		y = j - x - 1
	print(y, x, z)


arr = [int(input()) for i in range(int(input()))]
for n in arr:
	res = [n // 3 - 1, n // 3, n // 3 - 2]
	while sum(res) != n:
		if sum(res) > n:
			if res[2] >= res[0] - 3 and res[2] != 1:
				res[2] -= 1
			elif res[0] != 1:
				res[0] -= 1
		elif sum(res) < n:
			res[1] += 1
			res[0] += 1
			res[2] += 1
	print(*res)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 3 == 0:
		print(n // 3, n // 3 + 1, n // 3 - 1)
	elif n % 3 == 2:
		print(n // 3 + 1, n // 3 + 2, n // 3 - 1)
	elif n // 3 - 2 != 0:
		print(n // 3 + 1, n // 3 + 2, n // 3 - 2)
	else:
		print(n // 3, n // 3 + 2, n // 3 - 1)


t = int(input())
while t > 0:
	n = int(input())
	a = n + 3
	x = a // 3
	if (n + 3) % 3 == 0:
		print(f'{x - 1} {x} {x - 2}')
	elif n - 1 - 2 * x == 0:
		print(f'{x - 1} {x + 1} {n - 2 * x}')
	else:
		print(f'{x} {x + 1} {n - 1 - 2 * x}')
	t = t - 1


def main():
	t = int(input())
	for k in range(t):
		n = int(input())
		if n % 3 == 0:
			one = n // 3 + 1
		else:
			one = n // 3 + 2
		two = one - 1
		three = n - (one + two)
		if three == 0:
			three = 1
			two -= 1
		print(f'{two} {one} {three}')
main()


n = int(input())
ans = []
for i in range(n):
	m = int(input())
	if m % 3 == 0:
		a1 = int(m / 3) + 1
		a2 = int(m / 3)
		a3 = int(m / 3) - 1
	elif m % 3 == 1:
		a1 = int(m / 3) + 2
		a2 = int(m / 3) + 1
		a3 = int(m / 3) - 2
	else:
		a1 = int(m / 3) + 2
		a2 = int(m / 3) + 1
		a3 = int(m / 3) - 1
	if a3 == 0 and a1 > a2 + 1:
		a1 -= 1
		a3 += 1
	elif a3 == 0:
		a2 -= 1
		a3 += 1
	ans.append([a2, a1, a3])
for i in ans:
	for j in i:
		print(j, end=' ')
	print()


def solve():
	n = int(input())
	s = n % 3
	p = n // 3
	if s == 0:
		print(p, p + 1, p - 1)
	elif s == 1:
		if p != 2:
			print(p + 1, p + 2, p - 2)
		else:
			print(p, p + 2, p - 1)
	elif s == 2:
		print(p + 1, p + 2, p - 1)
T = int(input())
for _ in range(T):
	solve()


T = int(input())
for _ in range(T):
	n = int(input())
	x = n // 3
	y = n % 3
	if n == 7:
		print(2, 4, 1)
	elif y == 0:
		print(x, x + 1, x - 1)
	elif y == 1:
		print(x + 1, x + 2, x - 2)
	else:
		print(x + 1, x + 2, x - 1)