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\).