sng summer camp 5

B. 幂次转换

单点时限: 4.0 sec

内存限制: 256 MB

将一个正整数 $n$ 转化为 $a^b$ 的幂次形式,其中 $a \geqslant 2,b \geqslant 2$,$a,b$ 为正整数。
若 $n$ 无法进行这样的转化,请输出 n is powerless.,否则请输出整数n所有的幂次形式,输出格式如下:n=a1^b1=a2^b2=a3^b3=......,按照指数升序排列。

输入格式

第一行为数据组数 $T$,接下来 $T$ 行,每行输入一个正整数 $n$。
数据保证: $1 \leqslant T \leqslant 150, n \geqslant 1$

  • 测试点 1:$n \leqslant 100$
  • 测试点 2:$n \leqslant 10^5$
  • 测试点 3:$n \leqslant 10^{18}$

输出格式

对于每一组数据,如果能够进行幂次转化,按指定格式进行输出,否则输出格式形如:n is powerless.(n 是对应的输入数据)。

样例

Input
3
1
233
81
Output
1 is powerless.
233 is powerless.
81=9^2=3^4