题目描述

给你一个整数 $n$，你需要找三个正整数 $x,y,z$，满足 $n=x+y+z,x|n,y|n,z|n$，求最大的 $xyz$。

输入格式

第一行，一个正整数 $T$。

接下来 $T$ 行，每行一个整数 $n$，表示一个询问。

输出格式

对于每个询问，输出一行一个整数表示答案，如果无解输出 $-1$。

样例输入

3
1
2
3

-1
-1
1

数据范围

对于 $10 \%$ 的数据，满足 $T\le 10, 1\le n \le 1000$。

对于 $50 \%$ 的数据，满足 $T\le 10^3, 1\le n \le 10^6$。

对于 $100 \%$ 的数据，满足 $T \le 10^6, 1\le n \le 10^6$。