Maximum Split Product

You are given a positive integer n. Your task is to break n into a sum of at least two positive integers such that the product of these integers is maximized. For example, if n = 10, one optimal split is 3 + 3 + 4 and the product is 36.

Input: The first line contains an integer T, the number of test cases. Each of the following T lines contains a single integer n.

Output: For each test case, output a line containing the maximum product of non-zero parts that sum to n.

Note: It is assumed that 2 ≤ n ≤ 10⁶.

The optimal strategy is to split the number into as many 3’s as possible. However, if n is either 2 or 3, the answer is n-1.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T (the number of test cases). Each subsequent line contains a single integer n.

T
n1
n2
...
nT

outputFormat

For each test case, output the maximum product that can be obtained by splitting n into at least two positive summands. Each result should be printed on a new line to standard output (stdout).

result1
result2
...
resultT

## sample

3
2
10
15

1
36
243

</p>