codeforces#P1617B. GCD Problem

    ID: 32592 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>brute forceconstructive algorithmsmathnumber theory

GCD Problem

Description

Given a positive integer $n$. Find three distinct positive integers $a$, $b$, $c$ such that $a + b + c = n$ and $\operatorname{gcd}(a, b) = c$, where $\operatorname{gcd}(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

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

The first and only line of each test case contains a single integer $n$ ($10 \le n \le 10^9$).

For each test case, output three distinct positive integers $a$, $b$, $c$ satisfying the requirements. If there are multiple solutions, you can print any. We can show that an answer always exists.

Input

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

The first and only line of each test case contains a single integer $n$ ($10 \le n \le 10^9$).

Output

For each test case, output three distinct positive integers $a$, $b$, $c$ satisfying the requirements. If there are multiple solutions, you can print any. We can show that an answer always exists.

Samples

6
18
63
73
91
438
122690412
6 9 3
21 39 3
29 43 1
49 35 7
146 219 73
28622 122661788 2

Note

In the first test case, $6 + 9 + 3 = 18$ and $\operatorname{gcd}(6, 9) = 3$.

In the second test case, $21 + 39 + 3 = 63$ and $\operatorname{gcd}(21, 39) = 3$.

In the third test case, $29 + 43 + 1 = 73$ and $\operatorname{gcd}(29, 43) = 1$.