← 返回题目列表

Codeforces · 1665/A

A. GCD 与 LCM

中文机器翻译题面 查看原题

给你一个正整数$$$n$$$。你必须找到 $$$4$$$ 正整数 $$$a, b, c, d$$$ 使得

- $$$a + b + c + d = n$$$,并且
- $$$\gcd(a, b) = \operatorname{lcm}(c, d)$$$。

如果有多个可能的答案,您可以输出其中任何一个。可以证明答案总是存在的。

在此问题中,$$$\gcd(a, b)$$$ 表示 $$$a$$$ 和 $$$b$$$ 的最大公约数,$$$\operatorname{lcm}(c, d)$$$ 表示 $$$c$$$ 和 $$$d$$$ 的最小公倍数。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例都包含一行整数 $$$n$$$ ($$$4 \le n \le 10^9$$$) — $$$a$$$、$$$b$$$、$$$c$$$ 和 $$$d$$$ 的总和。

输出

对于每个测试用例输出 $$$4$$$ 正整数 $$$a$$$、$$$b$$$、$$$c$$$、$$$d$$$ 使得 $$$a + b + c + d = n$$$ 和 $$$\gcd(a, b) = \operatorname{lcm}(c, d)$$$。

示例

输入 #1

5
4
7
8
9
10

输出 #1

1 1 1 1
2 2 2 1
2 2 2 2
2 4 2 1
3 5 1 1

注意

在第一个测试用例中 $$$\gcd(1, 1) = \operatorname{lcm}(1, 1) = 1$$$, $$$1 + 1 + 1 + 1 = 4$$$。

在第二个测试用例中 $$$\gcd(2, 2) = \operatorname{lcm}(2, 1) = 2$$$, $$$2 + 2 + 2 + 1 = 7$$$。

在第三个测试用例中 $$$\gcd(2, 2) = \operatorname{lcm}(2, 2) = 2$$$, $$$2 + 2 + 2 + 2 = 8$$$。

在第四个测试用例中 $$$\gcd(2, 4) = \operatorname{lcm}(2, 1) = 2$$$, $$$2 + 4 + 2 + 1 = 9$$$。

在第五个测试用例中 $$$\gcd(3, 5) = \operatorname{lcm}(1, 1) = 1$$$, $$$3 + 5 + 1 + 1 = 10$$$。