Maximum Multiple

Time limit2sMemory limit256 MB

Summary

For each n, split it into three positive divisors x, y, z summing to n so that the product xyz is as large as possible, or report that no split exists.

Level: Medium6 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

Given an integer $n$ , Chiaki would like to find three positive integers $x$ , $y$ and $z$ such that: $n=x+y+z$ , $x\mid n$ , $y \mid n$ , $z \mid n$ and $xyz$ is maximum.

Input

There are multiple test cases. The first line of input contains an integer $T$ ( $1 \le T \le 10^6$ ), indicating the number of test cases. For each test case:

The first line contains an integer $n$ ( $1 \le n \le 10^{6}$ ).

Output

For each test case, output an integer denoting the maximum $xyz$ . If there no such integers, output $-1$ instead.

Examples1

Example 1
Input
```
3
1
2
3
```
Expected output
```
-1
-1
1
```