Maximum Multiple

n을 합이 n인 세 양의 약수 x, y, z로 나눠 곱 xyz를 최대로 만들고, 그런 분할이 없으면 -1을 출력한다.

보통6수학정수론완전 탐색아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제 설명

예제1

문제

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.