Background

Description

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。 如果一个数恰好等于它的真因子之和，则称该数为“完全数”。第一个完全数是6，第二个完全数是28，第三个完全数是496，后面的完全数还有8128、33550336等等。截至2018年，相关研究者已经找到51个完全数。

如果一个数恰好等于它的真因子之和，则称该数为“完全数” [2] 。各个小于它的约数（真约数，列出某数的约数，去掉该数本身，剩下的就是它的真约数）的和等于它本身的自然数叫做完全数（Perfect number），又称完美数或完备数。 例如：第一个完全数是6，它有约数1、2、3、6，除去它本身6外，其余3个数相加，1+2+3=6。第二个完全数是28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。第三个完全数是496，有约数1、2、4、8、16、31、62、124、248、496，除去其本身496外，其余9个数相加，1+2+4+8+16+31+62+124+248=496。后面的完全数还有8128、33550336等等。

特有性质 （1）所有的完全数都是三角形数。一定数目的点或圆在等距离的排列下可以形成一个等边三角形，这样的数被称为三角形数。例如：6=1+2+3；28=1+2+3+4+5+6+7；496=1+2+3+...+30+31；8128=1+2+3…+126+127。 （2）所有的完全数的倒数都是调和数。例如：1/1+1/2+1/3+1/6=2；1/1+1/2+1/4+1/7+1/14+1/28=2；1/1+1/2+1/4+1/8+1/16+1/31+1/62+1/124+1/248+1/496=2。 （3）可以表示成连续奇立方数之和。除6以外的完全数，都可以表示成连续奇立方数之和，并规律式增加。例如：28=13+3^3；496=1^3+3^3+5^3+7^3；8128=1^3+3^3+5^3+……+15^3；33550336=1^3+3^3+5^3+……+125^3+127^3。 （4）都可以表达为2的一些连续正整数次幂之和。不但如此，而且它们的数量为连续质数。例如：6=2^1+2^2；28=2^2+2^3+2^4；496=2^4+2^5+2^6+2^7+2^8；8128=2^6+2^7+2^8+2^9+2^10+2^11+2^12；33550336=2^12+2^13+……+2^24。 （5）完全数都是以6或8结尾。如果以8结尾，那么就肯定是以28结尾。（科学家仍未发现由其他数字结尾的完全数。） （6）各位数字辗转式相加个位数是1。除6以外的完全数，把它的各位数字相加，直到变成个位数，那么这个个位数一定是1。例如：28：2+8=10，1+0=1；496：4+9+6=19，1+9=10，1+0=1；8128：8+1+2+8=19，1+9=10，1+0=1；33550336:3+3+5+5+0+3+6=28,2+8=10,1+0=1。 （7）它们被3除余1、被9除余1、1/2被27除余1。除6以外的完全数，它们被3除余1，9除余1，还有1/2被27除余1。28/3 商9余1，28/9 商3余1，28/27 商1余1。496/3 商165余1，496/9 商55余1。8128/3 商2709余1，8128/9 商903余1，8128/27 商301余1。

Format

Input

Output

Samples

Limitation

1s, 1024KiB for each test case.