1041: Foney trick on CSyaonie

Time/Memory Limit:12000 MS/32768 K
Submitted: 38 Accepted: 17

 Problem Description

话说CSyaonie对数字是各种不敏感,foney为了帮助yaonie提起对数字的兴趣同时又想捉弄下yaonie就给他出了到非常简单的题目,题目的意思是这样的:给一个数字n,求n^n得到m,当这个m大于9时,就将它各个位上的数字相加得到结果,但当结果还是大于9时就重复这个过程,直到结果小于或等于9.例如n=4,则m=256,2+5+6=13,13大于9,1+3=4,4小于9即为结果。yaonie觉得so easy,并在1分钟内就敲好了代码,foney在测试时发现当n=16时,yaonie的结果是错误的,因为16^16=2^64,计算机表示不了那么大的数。于是可怜的妖孽只能求助于你,你能帮助他吗?

 Input

输入有多个测试实例,每个测试实例占一行,每行给一个正整数n(n<3999).当n=0时输入结束

 Output

对于每个实例输出占一行,每行给出题目所要求的答案

 Sample Input

2
3
4
0

 Sample Output

4
9
4

 Author

foney

 Recommend

zh