최대 곱

시간 제한2초메모리 제한256 MB

요약

각 n을 합이 n이 되는 세 양의 약수 x, y, z로 나누어 곱 xyz가 최대가 되게 하고, 그런 분할이 없으면 -1을 출력한다.

문제

정수 $n$ 이 주어졌을 때, Chiaki는 다음 조건을 만족하는 세 양의 정수 $x$ , $y$ , $z$ 를 찾으려고 한다: $n=x+y+z$ , $x\mid n$ , $y \mid n$ , $z \mid n$ 이고 $xyz$ 가 최대이다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ 가 주어진다 ( $1 \le T \le 10^6$ ). 각 테스트 케이스는 다음과 같다.

첫째 줄에 정수 $n$ 이 주어진다 ( $1 \le n \le 10^{6}$ ).

각 테스트 케이스마다 최대 $xyz$ 를 나타내는 정수를 출력한다. 그러한 정수가 없으면 $-1$ 을 출력한다.