You are given a positive integer $n$. You have to find $4$ positive integers $a, b, c, d$ such that

$a + b + c + d = n$, and

$\gcd(a, b) = \operatorname{lcm}(c, d)$.

If there are several possible answers you can output any of them. It is possible to show that the answer always exists.

In this problem $\gcd(a, b)$ denotes the greatest common divisor of $a$ and $b$, and $\operatorname{lcm}(c, d)$ denotes the least common multiple of $c$ and $d$.


-----Input-----

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

Each test case contains a single line with integer $n$ ($4 \le n \le 10^9$) — the sum of $a$, $b$, $c$, and $d$.


-----Output-----

For each test case output $4$ positive integers $a$, $b$, $c$, $d$ such that $a + b + c + d = n$ and $\gcd(a, b) = \operatorname{lcm}(c, d)$.


-----Examples-----

Input
5
4
7
8
9
10
Output
1 1 1 1
2 2 2 1
2 2 2 2
2 4 2 1
3 5 1 1


-----Note-----

In the first test case $\gcd(1, 1) = \operatorname{lcm}(1, 1) = 1$, $1 + 1 + 1 + 1 = 4$.

In the second test case $\gcd(2, 2) = \operatorname{lcm}(2, 1) = 2$, $2 + 2 + 2 + 1 = 7$.

In the third test case $\gcd(2, 2) = \operatorname{lcm}(2, 2) = 2$, $2 + 2 + 2 + 2 = 8$.

In the fourth test case $\gcd(2, 4) = \operatorname{lcm}(2, 1) = 2$, $2 + 4 + 2 + 1 = 9$.

In the fifth test case $\gcd(3, 5) = \operatorname{lcm}(1, 1) = 1$, $3 + 5 + 1 + 1 = 10$.

Difficulty: EASY
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
def main():
	for _ in range(int(input())):
		n = int(input())
		print(f'{n - 3} 1 1 1')
import sys
input = sys.stdin.readline
exit(main())


import sys
inp = sys.stdin.readline()
test = int(inp.strip('\n'))
result = ''
for i in range(test):
	inp = sys.stdin.readline()
	n = int(inp.strip('\n'))
	sys.stdout.write(str(n - 3) + ' 1 1 1\n')


import math
t = int(input())
res = []
for i in range(t):
	n = int(input())
	res.append(' '.join([str(n - 3), '1', '1', '1']))
for i in res:
	print(i)


def q(n):
	return str(n - 3) + ' 1' + ' 1' + ' 1'
n = int(input())
w = []
for i in range(n):
	w.append(q(int(input())))
for i in w:
	print(i)


def ans(n):
	return str(int(n - 3)) + ' 1 1 1'
x = int(input())
arr = []
for i in range(x):
	arr.append(int(input()))
for i in arr:
	print(ans(i))


n = int(input())
arr = []
for i in range(n):
	arr.append(int(input()))
for i in arr:
	print(str(1) + ' ' + str(i - 3) + ' ' + str(1) + ' ' + str(1))


import sys
for i in range(int(sys.stdin.readline())):
	k = int(sys.stdin.readline())
	print(k - 3, '1 1 1')


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	res.append((n - 3, 1, 1, 1))
for i in range(t):
	print(f'{res[i][0]} {res[i][1]} {res[i][2]} {res[i][3]}')


import sys
input = sys.stdin.readline
for ii in range(int(input())):
	n = int(input())
	print(n - 3, 1, 1, 1)


import sys

def main(num):
	return (num - 3, 1, 1, 1)
n = int(sys.stdin.readline().strip())
for i in range(n):
	num = int(sys.stdin.readline().strip())
	res = main(num)
	print(*res)


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
for t in wtf[1:]:
	n = int(t)
	print(f'{n - 3} 1 1 1')


import sys
input = sys.stdin.readline

def inp_int():
	return int(input())

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

def inp_string():
	s = input()
	return list(s[:len(s) - 1])

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

def solve():
	n = inp_int()
	print(n - 3, 1, 1, 1)
number_cases = inp_int()
for x in range(number_cases):
	solve()


for n in [*open(0)][1:]:
	print(int(n) - 3, 1, 1, 1)


for g in [*open(0)][1:]:
	print(int(g) - 3, 1, 1, 1)


import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	inp = int(input())
	if inp == 1:
		print('1 1 1 1')
	elif inp == 2:
		print('Mian_Talha_g')
	elif inp == 3:
		print('Talha_kite_Lover')
	else:
		count = 0
		count += inp - 3
		print(count, '1 1 1')


def solve(n):
	return f'{n - 3} 1 1 1'
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
	N = int(input())
	print(1, N - 3, 1, 1)


import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	print(n - 3, 1, 1, 1)


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	print(n - 3, 1, 1, 1)


from sys import stdin, stdout
t = int(stdin.readline())
for t_i in range(0, t):
	n = int(stdin.readline())
	half = n // 2
	a = n - 3
	c = 1
	b = 1
	d = 1
	print(a, b, c, d)


import sys
from typing import List

class Solution:

	def gcd_vs_lcm(self, total_sum: int) -> str:
		return ' '.join([str(total_sum - 3), '1', '1', '1'])
codeforce = Solution()
num_tests = int(sys.stdin.readline())
while num_tests > 0:
	data = int(sys.stdin.readline())
	print(codeforce.gcd_vs_lcm(data))
	num_tests -= 1


for i in [*open(0)][1:]:
	print(int(i) - 3, 1, 1, 1)


for t in [*open(0)][1:]:
	print(int(t) - 3, 1, 1, 1)


for l in [*open(0)][1:]:
	print(int(l) - 3, 1, 1, 1)


for x in [*open(0)][1:]:
	print(int(x) - 3, 1, 1, 1)


import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
t = int(input())
for _ in [0] * t:
	n = int(input())
	print(1, n - 3, 1, 1)


import sys
from collections import *

def prin(a):
	sys.stdout.write(str(a) + '\n')

def input():
	return sys.stdin.readline().strip()
mod = int(1000000000.0 + 7)
x8 = [-1, -1, 0, 1, 1, 1, 0, -1]
y8 = [0, 1, 1, 1, 0, -1, -1, -1]
for _ in range(int(input())):
	x = int(input())
	r = []
	r.append(x - 3)
	r.append(1)
	r.append(1)
	r.append(1)
	print(*r)


import sys
input = sys.stdin.readline
for iiii in range(int(input())):
	name = int(input())
	print(name - 3, 1, 1, 1)


import collections, math, bisect, sys
from collections import OrderedDict, Counter, defaultdict
from sys import stdin, stdout

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

def in1():
	return int(stdin.readline())

def display_arr(arr):
	stdout.write(' '.join(map(str, arr)) + '\n')

def display_num(num):
	stdout.write(str(num) + '\n')

def factorial(n):
	return n * factorial(n - 1) if n > 1 else 1

def percent(c, s):
	return c / s * 100

def l2d(a):
	return collections.Counter(a)

def lcm(x, y):
	return x * y // math.gcd(x, y)
a = []

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)
	return prime
for _ in range(in1()):
	n = in1()
	print(n - 3, 1, 1, 1)


tests = int(input())
arr = []
for _ in range(0, tests):
	arr.append(int(input()))
for i in range(0, tests):
	c = 1
	d = 1
	b = 1
	a = arr[i] - 3
	print(a, b, c, d)


cantidad = int(input())
x = []
for i in range(cantidad):
	x.append(int(input()))
for num in x:
	print(num - 3, 1, 1, 1)


def compute(n):
	return [n - 3, 1, 1, 1]
t = int(input())
main = []
for i in range(t):
	a = int(input())
	main.append(a)
for i in range(len(main)):
	string = ''
	for j in compute(main[i]):
		string += str(j) + ' '
	print(string)


import math
import sys
from collections import deque
import heapq

def inp():
	return sys.stdin.readline().rstrip()

def mpp():
	return map(int, inp().split())

def lis():
	return list(mpp())

def main():
	t = int(inp())
	for _ in range(t):
		n = int(inp())
		print(n - 3, 1, 1, 1)
main()


a = int(input())
c = []
d = 0
for i in range(0, a):
	z = int(input())
	c.append(z)
for b in c:
	print(b - 3, 1, 1, 1)


x = int(input(''))
z = []
for i in range(x):
	z.append(int(input('')))
for i in z:
	print(i - 3, 1, 1, 1)


T = int(input())
for t in range(1, T + 1):
	n = int(input())
	print('{} {} {} {}'.format(n - 3, 1, 1, 1))


alpha = []
beta = []
gamma = []
t = int(input())
for i in range(t):
	n = int(input())
	alpha.append(n)
for i in range(t):
	n = alpha[i]
	a = 1
	c = 1
	d = 1
	b = n - 3
	print(a, b, c, d)


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		print(n - 3, 1, 1, 1)
main()


problems = int(input())
for problem_no in range(problems):
	n = int(input())
	a = n - 3
	to_print = f'{a} 1 1 1'
	print(to_print)


import math
import sys
from typing import List

class Solution:

	def gcd_vs_lcm(self, total_sum: int) -> str:
		for num in range(total_sum - 3, 0, -1):
			if self.is_valid_answer([num, 1, 1, 1], total_sum, sum([3, num])):
				return ' '.join([str(num), '1', '1', '1'])

	def compute_lcm(self, x, y):
		lcm = x * y // math.gcd(x, y)
		return lcm

	def is_valid_answer(self, state: List[int], total_sum: int, current_sum: int) -> bool:
		if len(state) == 4 and current_sum == total_sum and (math.gcd(state[0], state[1]) == self.compute_lcm(state[2], state[3])):
			return True
		return False
codeforce = Solution()
num_tests = int(sys.stdin.readline())
while num_tests > 0:
	data = int(sys.stdin.readline())
	print(codeforce.gcd_vs_lcm(data))
	num_tests -= 1


import sys
input = lambda : sys.stdin.readline().strip()
n = int(input())
for i in range(n):
	x = int(input())
	print(x - 3, 1, 1, 1)


for _ in range(int(input())):
	n = int(input())
	print(str(n - 3) + ' 1 1 1')


tests = int(input())
for _ in range(tests):
	n = int(input())
	a = n - 3
	print(f'{a} 1 1 1')


tc = int(input())
for _ in range(tc):
	x = int(input())
	print(str(x - 3) + ' 1 1 1')


def solve(n):
	return f'{n - 3} {1} {1} {1}'
t = int(input())
for T in range(t):
	n = int(input())
	print(solve(n))


for num in range(int(input())):
	print(str(int(input()) - 3) + ' 1 1 1')


for _ in range(int(input())):
	n = int(input())
	print(f'{n - 3} 1 1 1')


t = int(input())
for i in range(t):
	n = int(input())
	print(n - 3, '1 1 1')


T = int(input())
for i in range(T):
	tmp1 = input()
	print('1 %i 1 1' % (int(tmp1) - 3))


for t in range(int(input())):
	n = int(input())
	print(f'{n - 3} 1 1 1')


t = int(input())
lst = []
for x in range(t):
	y = int(input())
	lst.append(y)
for i in lst:
	print(int(i - 3), int(1), int(1), int(1))


t = int(input())
matrix = []
for i in range(t):
	n = int(input())
	lis = [1, n - 3, 1, 1]
	matrix.append(lis)
l = len(matrix)
for i in range(l):
	print(matrix[i][0], matrix[i][1], matrix[i][2], matrix[i][3])


t = int(input())
for i in range(t):
	n = int(input())
	ans = str(n - 3) + ' 1 1 1'
	print(ans)


for _ in [0] * int(input()):
	print(f'1 {int(input()) - 3} 1 1')


n = int(input())
for m in range(0, n):
	i = int(input())
	print(f'{i - 3} 1 1 1')


t = int(input(), base=10)
for _ in range(t):
	n = int(input())
	if n >= 4:
		print(f'{n - 3} 1 1 1')


t = int(input())
while t:
	n = int(input())
	print(n - 3, '1 ' * 3)
	t -= 1


t = int(input())
for i in range(0, t):
	n = int(input())
	print('{} {} {} {}'.format(n - 3, 1, 1, 1))


t = int(input())

def q(n):
	return str(n - 3) + ' 1 1 1'
for i in range(t):
	n = int(input())
	print(q(n))


for case in range(int(input())):
	print(f'{int(input()) - 3} 1 1 1')


ti = int(input())
for i in range(ti):
	nn = int(input())
	print('1 ' + str(nn - 3) + ' 1 1')


a = int(input())
for i in range(0, a):
	n = int(input())
	if n >= 4 and n <= 10 ** 9:
		print(str(n - 3) + ' ' + '1' + ' ' + '1' + ' ' + '1')


import math
for _ in range(int(input())):
	n = int(input())
	ans = str(n - 3) + ' 1 1 1'
	print(ans)