408982: GYM103401 K Simple Math
Description
Recently, zyw is very interested in number theory. He find a very hard question:
Give a integer $$$n$$$, try to find $$$3$$$ integers $$$x$$$,$$$y$$$,$$$z$$$ satisfied $$$1 \leq x \leq y \leq z$$$ and $$$x+y+z=n$$$ makes the value of $$$gcd(x,y)+gcd(y,z)+gcd(z,x)$$$ as big as possible.
Zyw is a math genius and solved it in just $$$10^{-114514}$$$ second and it costs the judger 1000ms to give answer. Now he wants to know whether there is a faster way to solve it.
InputFirst line gives a integer $$$T$$$, represents the number of problems you should solve.
Next $$$T$$$ lines, each line gives a integer $$$n_i$$$, represent the $$$n$$$ in the legend for each problem.
$$$1 \leq T \leq 10^4.$$$
$$$3 \leq n_i \leq 10^9.$$$
Output$$$T$$$ lines, each line has three integers, represents $$$x$$$,$$$y$$$,$$$z$$$.
If there are more than $$$1$$$ solutions, output any of it.
ExampleInput1 3Output
1 1 1