U112555 普及模拟赛1_T2

有n个数字分别为$a_1$...$a_n$ 定义一个数字是幸运数:它可以表示为每一位上的数的k次方和。 例如$153=1^3+5^3+3^3$，此时k=3； 例如$4151=4^5+1^5+5^5+1^5$,此时k=5； 其中k是个自然数； 现在给定n个数，这n个数字中，有几个数字是幸运数？

第一行一个整数N； 接下来N行，每行一个整数，表示要判断的整数$a_i$。

先输出若干行，每行两个整数$a_j$,$k_j$ 表示n个数中每个符合要求的答案，第一个数表示原数，第二个数表示这个数拆开后的$k_j$次方满足条件。 以上答案按给定的数字顺序输出符合的答案，如果有多个$k_j$满足条件，输出最小的即可。 最后一行再一个整数，表示N个数中，多少个数满足条件。

100% 的数据， $1≤n≤100000,1≤a_i≤10^6$