시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB72353052.632%

문제

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.

입력

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}$).

출력

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

예제 입력 1

3
1
2
3

예제 출력 1

-1
-1
1