408982: GYM103401 K Simple Math

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.

First 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.$$$

$$$T$$$ lines, each line has three integers, represents $$$x$$$,$$$y$$$,$$$z$$$.

If there are more than $$$1$$$ solutions, output any of it.

1
3

1 1 1