##背景##
原题P1229用枚举可以过，所以就想到扩大数据范围让大家模拟下。

##描述##
一个自然数N的正因子个数记为F(N)，例如18的所有正因子为1、2、3、6、9、18，所以F(18)=6。现在给出K，求所有满足F(N)=K的N中最小的数.

##输入格式##
第一行n，表示有n个数据,1<=n<=10
接下来n行，每行一个数k，1<=k<=65536

##输出格式##
输出n行，每行一个解
对于每个解，按照算术基本定理输出它的素数唯一分解，例如：
如果解是6936，则输出2^3*3*17^2(按素因子从小到大的顺序)

##样例输入##
2
5
7

##样例输出##
2^4
2^6

##限制##
各个测试点1s

##提示##
前文已经给了hint

##来源##
改编自P1229