It is the easy version of the problem. The only difference is that in this version $k = 3$.

You are given a positive integer $n$. Find $k$ positive integers $a_1, a_2, \ldots, a_k$, such that:

$a_1 + a_2 + \ldots + a_k = n$

$LCM(a_1, a_2, \ldots, a_k) \le \frac{n}{2}$

Here $LCM$ is the least common multiple of numbers $a_1, a_2, \ldots, a_k$.

We can show that for given constraints the answer always exists.


-----Input-----

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

The only line of each test case contains two integers $n$, $k$ ($3 \le n \le 10^9$, $k = 3$).


-----Output-----

For each test case print $k$ positive integers $a_1, a_2, \ldots, a_k$, for which all conditions are satisfied.


-----Examples-----

Input
3
3 3
8 3
14 3
Output
1 1 1
4 2 2
2 6 6


-----Note-----

None

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Constructive algorithms


Solutions:
for s in [*open(0)][1:]:
	(n, _) = map(int, s.split())
	if n & 1:
		print(n // 2, n // 2, 1)
	elif n // 2 & 1:
		print(n // 2 - 1, n // 2 - 1, 2)
	else:
		print(n // 2, n // 4, n // 4)


def lcmno(n):
	if n % 2 == 0:
		if n % 4 == 0:
			a1 = str(n // 2)
			a2 = str(n // 4)
			return a1 + ' ' + a2 + ' ' + a2
		else:
			a1 = str((n - 2) // 2)
			a2 = '2'
			return a1 + ' ' + a1 + ' ' + a2
	else:
		a = str((n - 1) // 2)
		return '1' + ' ' + a + ' ' + a
t = input()
no = int(t)
s = ''
for i in range(no):
	r2 = input().split(' ')
	s += lcmno(int(r2[0])) + '\n'
print(s)


for i in [*open(0)][1:]:
	(n, k) = map(int, i.split())
	print(*[(n // 2, n // 4, n // 4), (n // 2, n // 2, 1), ((n - 1) // 2, (n - 1) // 2, 2), (n // 2, n // 2, 1)][n % 4])


import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
testcases = int(input())
for testcase in range(testcases):
	temparr = get_ints()
	a = temparr[0]
	b = temparr[1]
	ans = []
	if a == 4:
		print('2 1 1')
	elif a & 1:
		ans.append(str(1))
		a -= 1
		diff = a >> 1
		ans.append(str(diff))
		ans.append(str(diff))
		print(' '.join(ans))
	else:
		diff = a >> 1
		ans = []
		if diff & 1:
			ans.append(str(2))
			ans.append(str(diff - 1))
			ans.append(str(diff - 1))
			print(' '.join(ans))
		else:
			halfhalf = diff >> 1
			ans.append(str(diff))
			ans.append(str(halfhalf))
			ans.append(str(halfhalf))
			print(' '.join(ans))


def answer(n, k):
	if n % 4 == 0:
		return ' '.join(map(str, [n // 2, n // 4, n // 4]))
	elif n % 2 == 0:
		return ' '.join(map(str, [n // 2 - 1, n // 2 - 1, 2]))
	else:
		return ' '.join(map(str, [n // 2, n // 2, 1]))

def main():
	t = int(input())
	n = [0] * t
	k = [0] * t
	for j in range(t):
		(n[j], k[j]) = [int(i) for i in input().split()]
	for j in range(t):
		print(answer(n[j], k[j]))
main()


import sys
input = sys.stdin.readline
ins = lambda : input().rstrip()
ini = lambda : int(input().rstrip())
inm = lambda : map(int, input().rstrip().split())
inl = lambda : list(map(int, input().split()))
out = lambda x, s='\n': print(s.join(map(str, x)))
t = ini()
for _ in range(t):
	(n, k) = inm()
	if n % 2:
		print(1, n // 2, n // 2)
	else:
		x = n // 2
		if x % 2:
			print(2, x - 1, x - 1)
		else:
			print(x, x // 2, x // 2)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % 2:
		print(n // 2, n // 2, 1)
	elif n % 4:
		print(n // 2 - 1, n // 2 - 1, 2)
	else:
		print(n // 2, n // 4, n // 4)


def klcm(n, k):
	if n % 2 == 1:
		return [1, n // 2, n // 2]
	if n // 2 % 2 == 1:
		return [2, n // 2 - 1, n // 2 - 1]
	else:
		return [n // 4, n // 4, n // 2]
ans = []
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ans.append(klcm(n, k))
for i in ans:
	i = list(map(str, i))
	print(' '.join(i))


import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def solve(n):
	if n % 4 == 1:
		return (1, n // 2, n // 2)
	elif n % 4 == 2:
		return (2, (n - 2) // 2, (n - 2) // 2)
	elif n % 4 == 3:
		return (1, n // 2, n // 2)
	else:
		return (n // 4, n // 4, n // 2)
T = int(input())
for i in range(T):
	(n, k) = get_ints()
	(a, b, c) = solve(n)
	print(a, b, c)


t = int(input())
out = []
for _ in range(t):
	(n, k) = map(int, input().split())
	if n % 2 == 0:
		if n % 4 == 0:
			out.append([n // 2, n // 4, n // 4])
		else:
			out.append([n // 2 - 1, n // 2 - 1, 2])
	else:
		out.append([n // 2, n // 2, 1])
for i in out:
	print(*i)


from collections import defaultdict
from sys import stdin
input = lambda : stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	if n % 2 == 0:
		if n % 3 == 0:
			print(n // 3, n // 3, n // 3)
		elif n % 4 == 0:
			print(n // 2, n // 2 // 2, n // 2 // 2)
		else:
			print(2, (n - 2) // 2, (n - 2) // 2)
	else:
		print(1, n // 2, n // 2)


import sys
import math as mt
import collections as cc
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(n, k) = I()
	if n % 2:
		print(n // 2, n // 2, 1)
	elif n % 4 == 0:
		print(n // 2, n // 4, n // 4)
	else:
		print(2, n // 2 - 1, n // 2 - 1)


import sys
for _ in range(int(input())):
	(n, k) = map(int, sys.stdin.readline().split())
	(q, r) = divmod(n, 4)
	(a, b, c) = (0, 0, 0)
	if r == 0:
		(a, b, c) = (q, q, 2 * q)
	elif r == 2:
		(a, b, c) = (2, (n - 2) // 2, (n - 2) // 2)
	else:
		(a, b, c) = (1, n // 2, n // 2)
	print(a, b, c)


t = int(input())
result = []
for i in range(t):
	(n, k) = [int(x) for x in input().strip().split(' ')]
	res = ''
	if k > 3:
		res += ' '.join(['1'] * (k - 3)) + ' '
		n -= k - 3
	if n % 2 == 1:
		result.append(f'{res}{n // 2} {n // 2} 1')
	else:
		half = n // 2
		if half % 2 == 0:
			result.append(f'{res}{half} {half // 2} {half // 2}')
		else:
			result.append(f'{res}{half - 1} {half - 1} 2')
for line in result:
	print(line)


import sys
from math import log

def solve(n, k):
	if 2 ** int(log(n, 2)) == n:
		return ' '.join([str(n // 2), str(n // 4), str(n // 4)])
	else:
		if n % 2 == 1:
			c = 1
			a = (n - 1) // 2
			b = a
			return ' '.join([str(a), str(b), str(c)])
		counter = 2
		while counter < n:
			if n % counter == 0:
				if n // counter % 2 == 1:
					a = counter
					b = counter * (n // counter - 1) // 2
					c = b
					return ' '.join([str(a), str(b), str(c)])
			counter += 2
	return None
t = int(sys.stdin.readline().strip())
ans = 0
for _ in range(t):
	line = sys.stdin.readline().strip()
	(n, k) = list(map(int, line.split()))
	print(solve(n, k))


import sys
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	half = n // 2
	if not n % 2 and (not half % 2):
		print(half, half // 2, half // 2)
	elif not n % 2 and half % 2:
		half -= 1
		print(half, half, 2)
	else:
		print(half, half, 1)


import math, sys
for _ in range(int(input())):
	n = int(sys.stdin.readline().split()[0])
	if n % 2 == 0:
		if n % 4 == 0:
			print(int(n / 2), int(n / 4), int(n / 4))
		else:
			print(int(n / 2 - 1), int(n / 2 - 1), 2)
	else:
		print(1, math.floor(n / 2), math.floor(n / 2))


list_ans = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = 0
	while n % 2 == 0:
		n //= 2
		a += 1
	if n == 1:
		list_ans.append(str(2 ** (a - 2)) + ' ' + str(2 ** (a - 2)) + ' ' + str(2 ** (a - 1)))
	else:
		list_ans.append(str(2 ** a) + ' ' + str(2 ** a * (n - 1) // 2) + ' ' + str(2 ** a * (n - 1) // 2))
print(*list_ans, sep='\n')


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	(n, k) = M()

	def solve(n):
		a = []
		if n % 2 == 1:
			a = [n // 2, n // 2, 1]
		elif n % 4 != 0:
			a = [n // 2 - 1, n // 2 - 1, 2]
		else:
			a = [n // 4, n // 4, n // 2]
		return a
	print(*[1] * (k - 3) + solve(n - k + 3))


import math
import sys
import collections
import bisect
import time

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
for t in range(int(input())):
	(n, k) = get_ints()
	ans = []
	while k > 3:
		ans.append(1)
		k -= 1
		n -= 1
	if n % 2 == 0:
		if n % 4 == 0:
			ans.append(n // 2)
			ans.append(n // 4)
			ans.append(n // 4)
		else:
			ans.append(n // 2 - 1)
			ans.append(n // 2 - 1)
			ans.append(2)
	else:
		ans.append(1)
		ans.append((n - 1) // 2)
		ans.append((n - 1) // 2)
	print(*ans)


import sys
import math
import bisect
import collections
input = sys.stdin.readline

def inp():
	return int(input())

def inplist():
	return list(map(int, input().split()))

def inpstrlist():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def printlist(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')
t = int(input())
for _ in range(t):
	(n, m) = invr()
	if n % 2 == 0:
		if n % 4 == 0:
			print(n // 2, n // 4, n // 4)
		else:
			x = n // 2 - 1
			print(x, x, 2)
	else:
		x = n // 2
		print(x, x, 1)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	k = inputs[1]
	if n % 2 == 1:
		print(f'{n // 2} {n // 2} 1')
	else:
		half = n // 2
		if half % 2 == 0:
			print(f'{half} {half // 2} {half // 2}')
		else:
			print(f'{half - 1} {half - 1} 2')


import math
answers = []

def solve(n, k):
	if n % 3 == 0:
		res = n // 3
		answers.append([res, res, res])
		return
	if n % 4 == 0:
		a1 = n // 4
		a2 = n // 2
		answers.append([a2, a1, a1])
		return
	if n % 2 == 1:
		res = n // 2
		answers.append([1, res, res])
		return
	if n % 2 == 0 and n % 4 == 2:
		rem = (n - 2) // 2
		answers.append([2, rem, rem])
		return
T = int(input())
while T:
	(n, k) = [int(x) for x in input().split()]
	solve(n, k)
	T -= 1
for ans in answers:
	print(*ans)


from math import floor

def lcm(n):
	if n % 2 != 0:
		return [1, floor(n / 2), floor(n / 2)]
	elif n % 2 == 0 and n % 4 != 0:
		return [n // 2 - 1, n // 2 - 1, 2]
	else:
		return [n // 2, n // 4, n // 4]
t = int(input())
answer = []
for _ in range(t):
	(n, k) = map(int, input().split())
	answer.append(lcm(n))
for i in answer:
	print(*i)


import sys

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def rinput():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))
t = iinput()
for _ in range(t):
	(n, k) = rinput()
	if n % 2 == 0:
		a = (n - 2) / 2
		if a % 2 == 0:
			a = 2
			b = (n - 2) / 2
		else:
			a = n / 2
			b = n / 4
	else:
		a = 1
		b = (n - 1) / 2
	print(int(a), int(b), int(b))


import sys
for i in range(int(sys.stdin.readline())):
	(n, k) = map(int, sys.stdin.readline().split())
	ans = []
	if n == 3:
		ans = [1, 1, 1]
	else:
		k = n // 4
		if n % 4 == 0:
			ans = [k, k, 2 * k]
		elif n % 4 == 1:
			ans = [2 * k, 2 * k, 1]
		elif n % 4 == 2:
			ans = [2 * k, 2 * k, 2]
		else:
			ans = [2 * k + 1, 2 * k + 1, 1]
	print(*ans)


import math

def main_function():
	testcases = range(int(input()))
	for test in testcases:
		(n, k) = [int(i) for i in input().split(' ')]
		if n % 2 == 1:
			print(' '.join([str(1), str((n - 1) // 2), str((n - 1) // 2)]))
		elif n % 4 == 0:
			print(' '.join([str(n // 2), str(n // 4), str(n // 4)]))
		else:
			z = n // 2
			print(' '.join([str(z - 1), str(z - 1), str(2)]))
main_function()


def read_int():
	return int(input())

def read_ints():
	return map(int, input().split(' '))

def split_three(n):
	if n % 2 == 1:
		return [1, n // 2, n // 2]
	elif n % 4 == 2:
		return [2, n // 2 - 1, n // 2 - 1]
	else:
		return [n // 4, n // 4, n // 2]
t = read_int()
for case_num in range(t):
	(n, k) = read_ints()
	print(' '.join(map(str, split_three(n))))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if n % 2:
		print(n // 2, n // 2, 1)
	elif n // 2 % 2:
		print(n // 2 - 1, n // 2 - 1, 2)
	else:
		print(n // 2, n // 4, n // 4)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a & 1:
		print(1, a // 2, a // 2)
	elif a % 4 == 0:
		print(a // 2, a // 4, a // 4)
	else:
		print(2, a // 2 - 1, a // 2 - 1)


I = lambda : map(int, input().split())
for _ in [0] * int(input()):
	(n, _) = I()
	if n % 2 == 1:
		print(n // 2, n // 2, 1)
	elif n % 4 == 0:
		print(n // 2, n // 4, n // 4)
	else:
		print(n // 2 - 1, n // 2 - 1, 2)


t = int(input().strip())
for i in range(t):
	(n, _) = list(map(int, input().strip().split()))
	if n % 2 == 1:
		print('{} {} {}'.format(1, (n - 1) // 2, (n - 1) // 2))
	elif n % 4 == 0:
		print('{} {} {}'.format(n // 2, n // 4, n // 4))
	else:
		print('{} {} {}'.format(2, n // 2 - 1, n // 2 - 1))


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	inp += [input()]
for i in inp:
	n = int(i.split()[0])
	x = 1
	a = n
	while a % 2 == 0:
		x *= 2
		a = a // 2
	if a == 1:
		print(x // 2, x // 4, x // 4)
	else:
		print(x, x * (a - 1) // 2, x * (a - 1) // 2)


k = int(input())
sp = []
for i in range(k):
	(n, m) = list(map(int, input().split()))
	if n % 2 == 0:
		if n // 2 % 2 == 0:
			sp.append([n // 2, n // 2 // 2, n // 2 // 2])
		else:
			sp.append([2, (n - 2) // 2, (n - 2) // 2])
	else:
		sp.append([1, (n - 1) // 2, (n - 1) // 2])
for i in sp:
	print(*i, end='\n')


import math

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = list(map(int, input().split()))
		s = ''
		if n % 2 == 1:
			s += '1 '
			s += str(n // 2) + ' '
			s += str(n // 2) + ' '
		elif n % 4 == 0:
			s = str(2 * (n // 4)) + ' '
			s += str(n // 4) + ' '
			s += str(n // 4) + ' '
		else:
			s = '2 '
			s += str((n - 2) // 2) + ' '
			s += str((n - 2) // 2) + ' '
		print(s)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % 4 == 0:
		print(str(n // 4) + ' ' + str(n // 4) + ' ' + str(n // 2))
	elif n % 4 == 2:
		print(' '.join(['2', str((n - 2) // 2), str((n - 2) // 2)]))
	else:
		print(' '.join(['1', str((n - 1) // 2), str((n - 1) // 2)]))


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	if n % 2:
		print(f'1 {int((n - 1) / 2)} {int((n - 1) / 2)}')
	elif n % 4:
		print(f'2 {int((n - 2) / 2)} {int((n - 2) / 2)}')
	else:
		print(f'{int(n / 4)} {int(n / 4)} {int(n / 2)}')


cases = int(input())
for _ in range(0, cases):
	input1 = input().split()
	(n, k) = (int(input1[0]), int(input1[1]))
	if n % 2 == 1:
		print(n // 2, n // 2, 1)
	else:
		temp = int(n / 2)
		if temp % 2 == 0:
			print(temp, int(temp / 2), int(temp / 2))
		else:
			print(2, int(temp) - 1, int(temp) - 1)


def main():
	(n, k) = map(int, input().split())
	if n % 2 == 1:
		print(1, n // 2, n // 2)
		return
	if n % 4 == 0:
		print(n // 4, n // 4, n // 2)
		return
	else:
		print(2, (n - 2) // 2, (n - 2) // 2)
for _ in range(int(input())):
	main()


t = int(input())
for i in range(t):
	(n, k) = [int(num) for num in input().split(' ', 1)]
	x = n // 2
	lst = []
	if x % 2 == 0 and n % 2 == 0:
		anns = int(x / 2)
		print(anns, anns, x)
	elif x % 2 == 1 and n % 2 == 0:
		o = x - 1
		print(o, o, 2)
	elif n % 2 == 1:
		print(1, x, x)


t = eval(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n % 2 != 0:
		print(1, int(n // 2), int(n // 2))
	else:
		x = n // 2
		if x % 2 != 0:
			print(2, int(n // 2 - 1), int(n // 2 - 1))
		else:
			print(int(x // 2), int(x // 2), int(x))


(t, a1, a2, a3) = (int(input()), 0, 0, 0)
for x in range(t):
	(n, k) = map(int, input().split())
	if n % 2 != 0 or n // 2 % 2 != 0:
		a1 = round(n / 2 + 0.1) - 1
		a2 = round(n / 2 + 0.1) - 1
		a3 = n - a1 - a2
	else:
		a1 = n // 2
		a2 = n // 4
		a3 = n // 4
	print(a1, a2, a3)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n % 2 != 0:
		if n % 3 == 0:
			print(n // 3, n // 3, n // 3)
		else:
			print(n // 2, n // 2, 1)
	else:
		c = n // 2
		if c % 2 == 0:
			print(c // 2, c // 2, c)
		else:
			c -= 1
			print(c, c, n - 2 * c)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	a = [0] * 3
	v = n // 2
	if n % 3 == 0:
		print(str(n // 3) + ' ' + str(n // 3) + ' ' + str(n // 3))
		continue
	if n == 4:
		print('1 1 2')
		continue
	if n % 2 == 1:
		a = 1
		b = (n - 1) // 2
		print(str(a) + ' ' + str(b) + ' ' + str(b))
	elif n % 2 == 0:
		v = (n - 2) // 2
		if v % 2 == 0:
			print('2 ' + str(v) + ' ' + str(v))
		else:
			a = n // 4
			b = n // 2
			print(str(a) + ' ' + str(a) + ' ' + str(b))


from math import floor
test = int(input())
for t in range(test):
	(n, k) = list(map(int, input().split()))
	if n % 2 != 0:
		print(1, floor(n / 2), floor(n / 2))
	elif n % 4 == 0:
		print(n // 2, n // 4, n // 4)
	else:
		print(int(n / 2 - 1), int(n / 2 - 1), 2)


def ss(n):
	for i in range(1, 1 + n ** 0.5):
		if n % i == 0:
			return n // i
	return 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % 2 == 0:
		if n % 4 == 0:
			print(*[n // 2, n // 4, n // 4])
		else:
			print(*[2, n // 2 - 1, n // 2 - 1])
	else:
		print(*[1, n // 2, n // 2])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [1] * (k - 3)
	n -= k - 3
	if not n % 4:
		print(*a, n // 2, n // 4, n // 4)
	elif not n % 2:
		print(*a, n // 2 - 1, n // 2 - 1, 2)
	else:
		print(*a, n // 2, n // 2, 1)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	ans = n // 2
	if n % 2 == 0 and ans % 2 == 0:
		print(ans, ans // 2, ans // 2)
	elif n % 2 == 0 and ans % 2 != 0:
		print(ans - 1, ans - 1, 2)
	else:
		print(ans, ans, 1)


for i in range(int(input())):
	(n, b) = [int(x) for x in input().split()]
	if n % 4 == 0:
		print(n // 2, n // 4, n // 4)
	elif n % 4 == 2:
		print(n // 2 - 1, n // 2 - 1, 2)
	else:
		print(1, n // 2, n // 2)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	if n % 2:
		print('%d %d 1' % (n // 2, n // 2))
	elif n // 2 % 2:
		print('%d %d 2' % (n // 2 - 1, n // 2 - 1))
	else:
		print(n // 2, end=' ')
		print('%d %d' % (n // 2 // 2, n // 2 // 2))


T = int(input())

def solve(N, K):
	if K == 3:
		if N % 2 == 1:
			return [(N - 1) // 2, (N - 1) // 2, 1]
		elif N % 4 == 2:
			return [(N - 2) // 2, (N - 2) // 2, 2]
		elif N % 4 == 0:
			return [N // 2, N // 4, N // 4]
	return solve(N - (K - 3), 3) + [1] * (K - 3)
for _ in range(T):
	(N, K) = map(int, input().split())
	print(' '.join(map(str, solve(N, K))))


t = int(input())
while t > 0:
	t -= 1
	ip = input()
	n = int(ip.split()[0])
	if n % 2 == 1:
		ans = [n // 2, n // 2, 1]
	elif n % 4 == 0:
		ans = [n // 2, n // 4, n // 4]
	else:
		ans = [n // 2 - 1, n // 2 - 1, 2]
	print(*ans)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	if n & 1 == 0:
		if n // 2 & 1 == 0:
			print(n // 2, n // 4, n // 4)
		else:
			print(2, n // 2 - 1, n // 2 - 1)
	else:
		print(n // 2, n // 2, 1)
	t -= 1


for i in range(int(input())):
	(summ, k) = map(int, input().split())
	if summ % 4 == 0:
		print(summ // 2, summ // 4, summ // 4)
	elif summ % 2 == 0:
		print((summ - 2) // 2, (summ - 2) // 2, 2)
	else:
		print(1, (summ - 1) // 2, (summ - 1) // 2)


for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	if a % 2 == 1:
		print(a // 2, a // 2, 1)
	else:
		c = a // 2
		if c % 2 == 0:
			print(c, c // 2, c // 2)
		else:
			a = a - 2
			print(2, a // 2, a // 2)


import sys, time
from math import ceil, floor
fun = lambda : map(int, input().split())
for _ in range(int(input())):
	(n, k) = fun()
	ans = [[n // 2, n // 4, n // 4], [1, (n - 1) // 2, (n - 1) // 2], [2, (n - 2) // 2, (n - 2) // 2], [1, (n - 1) // 2, (n - 1) // 2]]
	print(*ans[n % 4])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % 3 == 0:
		print(n // 3, n // 3, n // 3)
	elif n % 2 == 1:
		print(1, (n - 1) // 2, (n - 1) // 2)
	elif n % 8 == 0:
		print(n // 2, n // 4, n // 4)
	elif n == 4:
		print(1, 1, 2)
	elif n // 2 % 2 == 1:
		print(2, (n - 2) // 2, (n - 2) // 2)
	else:
		print(4, (n - 4) // 2, (n - 4) // 2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % 2 == 1:
		print(n // 2, n // 2, 1)
	else:
		t = n // 2
		if t % 2 == 0:
			print(t // 2, t // 2, t)
		else:
			print(t - 1, 2, t - 1)


for x in range(int(input())):
	(n, k) = map(int, input().split())
	if n % 2 == 0:
		n = n // 2
		if n % 2 == 1:
			print(2, n - 1, n - 1)
		else:
			print(n, n // 2, n // 2)
	elif n % 2 == 1:
		print(n // 2, n // 2, 1)


for t in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if n % 4 == 0:
		print(n // 2, n // 4, n // 4)
	elif n % 2 == 0:
		print(n // 2 - 1, n // 2 - 1, 2)
	else:
		print(n // 2, n // 2, 1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if n % 3 == 0:
		print(n // 3, n // 3, n // 3)
	elif n % 2 == 1:
		print(1, n // 2, n // 2)
	else:
		ta = n // 2
		if ta % 2 == 0:
			print(ta, ta // 2, ta // 2)
		else:
			print(ta - 1, ta - 1, 2)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 3:
		if n % 2 == 1:
			print(1, (n - 1) // 2, (n - 1) // 2)
		else:
			m = n // 2
			if m % 2 == 1:
				print(2, m - 1, m - 1)
			else:
				print(m // 2, m // 2, m)


from math import floor
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	k = 3
	x = []
	if n % 2 == 0:
		if n / 2 % 2 == 0:
			x.append(int(n / 2))
			x.append(int(n / 2 / 2))
			x.append(int(n / 2 / 2))
		else:
			x.append(2)
			x.append(int(n / 2 - 1))
			x.append(int(n / 2 - 1))
	else:
		x.append(1)
		x.append(floor(n / 2))
		x.append(floor(n / 2))
	print(' '.join(map(str, x)))


test_num = int(input())

def solve():
	(n, k) = map(int, input().split())
	if n % 2 == 1:
		print(1, n // 2, n // 2)
	elif n % 4 == 2:
		print(2, n // 2 - 1, n // 2 - 1)
	else:
		print(n // 4, n // 4, n // 2)
for i in range(test_num):
	solve()


T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	if n == 4:
		print(1, 1, 2)
	elif n % 2 == 1:
		print((n - 1) // 2, (n - 1) // 2, 1)
	else:
		v = n // 2 - 1
		if v % 2 == 0:
			print(v, v, 2)
		else:
			print(n // 2, n // 4, n // 4)


def processing():
	(n, k) = [int(x) for x in input().split()]
	if n % 2 == 1:
		print(1, n // 2, n // 2, sep=' ', end='\n')
	elif n % 4 == 0:
		print(n // 2, n // 2 // 2, n // 2 // 2, sep=' ', end='\n')
	else:
		print(2, (n - 2) // 2, (n - 2) // 2, sep=' ', end='\n')
t = int(input())
for i in range(t):
	processing()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n % 2 == 0:
		if n / 2 % 2 == 0:
			print(n // 2, n // 4, n // 4)
		else:
			print(n // 2 - 1, n // 2 - 1, 2)
	else:
		print(1, n // 2, n // 2)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n % 2 == 0:
		if n % 4 == 0:
			lst = [n // 4, n // 4, n // 2]
		elif n % 3 == 0:
			lst = [n // 3, n // 3, n // 3]
		else:
			k = n
			while k % 4 != 0:
				k -= 2
			lst = [n - k, k // 2, k // 2]
	else:
		lst = [1, (n - 1) // 2, (n - 1) // 2]
	l1 = []
	for i in lst:
		l1.append(str(i))
	print(' '.join(l1))


n = int(input())
for i in range(n):
	(num, k) = map(int, input().split())
	if num % 2 == 0:
		if num % 4 == 0:
			print(num // 2, num // 4, num // 4)
		else:
			print(2, (num - 2) // 2, (num - 2) // 2)
	else:
		print(1, (num - 1) // 2, (num - 1) // 2)


def solve(n, k):
	if n % 3 == 0:
		m = n // 3
		print(m, m, m)
	elif n % 4 == 0:
		m = n // 4
		print(2 * m, m, m)
	elif n % 4 == 2:
		m = n // 4
		print(2 * m, 2 * m, 2)
	else:
		m = n // 2
		print(m, m, 1)
for case in range(int(input())):
	(n, k) = map(int, input().split())
	ans = solve(n, k)