Construct Three Integers to Satisfy a GCD and LCM Equation

Given a positive integer (a), find three positive integers (b, c, d) (with (b, c, d \le 1,634,826,193)) such that: [ a+b+c+d = \gcd(a,b) + \operatorname{lcm}(c,d). ] There are multiple test cases in one input. If there are several solutions, output any valid one.

Hint: A constructive solution exists. For example, one valid approach is to fix (b=1) so that (\gcd(a,1)=1), and then choose (c) and (d) such that [ \operatorname{lcm}(c,d)=a+c+d. ] One way to achieve this is as follows. Let (g) be the largest power of 2 dividing (a) (i.e. (g = a \mathbin{&} (-a))). Then set:

• (b = 1),
• (c = 2g),
• (d = a+2g).

It can be verified that these choices satisfy [ a+1+2g+(a+2g)= a+1+2a+4g = 2a+4g+1 ] and since [ \gcd(a,1)=1, \quad \operatorname{lcm}(2g,a+2g)= \frac{2g,(a+2g)}{\gcd(2g,a+2g)} ] one may show that indeed [ a+1+2g+(a+2g)=1+\operatorname{lcm}(2g,a+2g). ] A proof of correctness is left as an exercise.

Note: It is guaranteed that the numbers (b, c, d) chosen by this method respect the required bound if (a) is not too large.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains one positive integer \(a\).

outputFormat

For each test case, output three positive integers \(b, c, d\) separated by spaces which satisfy the equation \(a+b+c+d = \gcd(a,b)+\operatorname{lcm}(c,d)\).

sample

3
1
2
3

1 2 3
1 4 6
1 2 5