题目描述

如果在一个固定的进制中，一个n位自然数等于自身各个数位上数字的n次幂之和，则称此数为自幂数。

例如：在十进制中，153是一个三位数，各个数位的3次幂之和为1^3+5^3+3^3=153，所以153是十进制中的自幂数。

在n进制中，所有小于n的正整数都为自幂数，比如2进制中1是自幂数，3进制中1和2都是自幂数，4进制中1，2和3都是自幂数...... 种自幂数的名称

一位自幂数：独身数

两位自幂数：没有

三位自幂数：水仙花数

四位自幂数：[四叶玫瑰数]

五位自幂数：五角星数

六位自幂数：六合数

七位自幂数：北斗七星数

八位自幂数：八仙数

九位自幂数：九九重阳数

十位自幂数：十全十美数

独身数共有10个: 0，1，2，3，4，5，6，7，8，9；

水仙花数共有4个：153，370，371，407；

四叶玫瑰数共有3个：1634，8208，9474；

五角星数共有3个：54748，92727，93084；

六合数只有1个：548834；

北斗七星数共有4个：1741725，4210818，9800817，9926315；

八仙数共有3个：24678050，24678051，88593477

……

使用高精度计算，可以得到超过int类型上限的水仙花数：

5: 93084

5: 92727

5: 54748

6: 548834

7: 9800817

7: 4210818

7: 1741725

7: 9926315

8: 24678050

8: 24678051

8: 88593477

9: 146511208

9: 472335975

9: 534494836

9: 912985153

10: 4679307774

11: 32164049650

11: 32164049651

11: 40028394225

11: 42678290603

11: 44708635679

11: 49388550606

11: 82693916578

11: 94204591914

14: 28116440335967

16: 4338281769391370

16: 4338281769391371

17: 21897142587612075

17: 35641594208964132

17: 35875699062250035

19: 1517841543307505039

19: 3289582984443187032

19: 4929273885928088826

19: 4498128791164624869

20: 63105425988599693916

21: 449177399146038697307

21: 128468643043731391252

23: 27907865009977052567814

23: 35452590104031691935943

23: 27879694893054074471405

23: 21887696841122916288858

24: 174088005938065293023722

24: 188451485447897896036875

(为环保起见，24位以上的自幂数略)

十进制中最大的自幂数有39位，共有88个自幂数。

Format

Input

Output

Samples

5

1:0 1 2 3 4 5 6 7 8 9 
2:
3:153 370 371 407 
4:1634 8208 9474 
5:54748 92727 93084

Limitation

60s, 1024KiB for each test case.