Description

为了迎接圣诞，信息学兴趣小组的同学们在辅导老师的带领下，举办了一个盛大的晚会，晚会的第一项内容是做游戏：猜数。老师给每位同学发一张卡片，每张卡片上都有一个编号（此编号为非负数，且小于255），每个编号互不相同。老师制定了以下的游戏规则：第一轮，每位同学将自己卡片上编号的各位数字进行平方后再相加得到一组新数，编号在这组新数中出现的同学淘汰出局；第二轮，余下的同学再将编号的各位数字进行立方相加得到一组新数，编号在这组新数中出现的同学再淘汰出局；第三轮，余下的同学再将编号的各位数字进行4次方相加得到一组新数，编号在这组新数中出现的同学再淘汰出局，依此类推，经过n轮后，仍留下来的同学，将获得圣诞特别礼物，卡片上的数即是2008年吉祥数。（假定班级人数不超过200人）

Input

输入第一行为一个整数n（1<=n<8），表示有n轮游戏。 第二行是卡片上互不相同的编号，每两个编号间有一个空格。

Output

输出只有一行，为剩下来的各个吉祥数，按从小到大顺序输出，每两个数之间有一个空格。

Samples

1
24 123 2 12 20 14 4 6 36 72

2 6 12 24 72 123

Limitation

1s, 1024KiB for each test case.