← 返回题目列表

Codeforces · 1617/B

B. GCD问题

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

给定一个正整数 $$$n$$$。找到三个不同的正整数 $$$a$$$、$$$b$$$、$$$c$$$,使得 $$$a + b + c = n$$$ 且 $$$\operatorname{gcd}(a, b) = c$$$,其中 $$$\operatorname{gcd}(x, y)$$$ 表示整数 $$$x$$$ 的最大公约数 (GCD), $$$y$$$。

输入

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

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$10 \le n \le 10^9$$$)。

输出

对于每个测试用例,输出满足要求的三个不同的正整数$$$a$$$、$$$b$$$、$$$c$$$。如果有多个解决方案,您可以打印任何一个。我们可以证明答案总是存在的。

示例

输入 #1

6
18
63
73
91
438
122690412

输出 #1

6 9 3
21 39 3
29 43 1
49 35 7
146 219 73
28622 122661788 2

注意

在第一个测试用例中,$$$6 + 9 + 3 = 18$$$ 和 $$$\operatorname{gcd}(6, 9) = 3$$$。

在第二个测试用例中,$$$21 + 39 + 3 = 63$$$ 和 $$$\operatorname{gcd}(21, 39) = 3$$$。

在第三个测试用例中,$$$29 + 43 + 1 = 73$$$ 和 $$$\operatorname{gcd}(29, 43) = 1$$$。