18977번 - Maximum Multiple 다국어

문제

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.

제한

힌트