Given integer $N$, you need to find four integers $A,B,C,D$, such that they're all factors of $N$ ($A|N,B|N,C|N,D|N$), and $N=A+B+C+D$. Your goal is to maximize $A\times B\times C\times D$.

Input format

First line contains an integer $T(1\le T\le 4\cdot 10^4)$, represents the number of test cases.

Each of the next $T$ lines contains an integer $N$ ($1\le N\le 4\cdot 10^4$, $N^4$ will not exceed 64 bit integer).

Output format

$T$ lines, each line contains the answer ($A\times B\times C\times D$) to correspond test case. If there is no way to find such four numbers, output $-1$.