题目描述

史密斯数（Smith number）有如下特点：各位上的数字相加等于分解质因数后各位上的数字相加，并且本身不是素数。

以4937775为例，先将4937775分解质因数：4937775=3×5×5×65837，然后再把4937775所有质因数各位上的数字相加得：3+5+5+6+5+8+3+7=42，接着他又把4937775各位上的数字相加得：4+9+3+7+7+7+5=42。所以4937775是一个史密斯数。 


 


现在给你一个数，请你给出大于这个数的最小史密斯数

输入格式

有一列数据，每行一个正整数n

n8 


最后有一个数字0，表示输入结束

输出格式

对每行的正整数n，给出大于n的最小史密斯数，输出一行

4937774
4937775
4937776
0

4937775
4937818
4937818