Problem Description

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.

3
1
2
3

-1
-1
1