數論 - UVA 10042 - Smith Number

UVA 10042 - Smith Number

問題

有一個叫Albert Wilansky的數學家有一次在翻他的電話簿時意外的發現他的小舅子的電話號碼有一個很奇妙的特性。所有數字的總和等於其所有因數數字的總和。實例說明：他小舅子的電話是493-7775。這個數可以被因數分解成4937775=3*5*5*65837。所以原數字的各數字總和等於4+9+3+7+7+7+5=42。所有因數的各數字總和等於3+5+5+6+5+8+3+7=42。
Wilansky很驚訝於他的發現並且把這種數字以他小舅子的名字Smith來命名。

經過觀察，所有的質數都符合以上的條件，所以Wilanksy稍後把質數排除在Smith Numbers的定義之外（也就是說所有得質數都不是Smith Numbers）。

* 中文翻譯：Lucky 貓

Input

第1行有1個整數告訴你接下來共有多少行測試資料。每行測試資料有一個正整數 n（n<10⁹）

Output

對每個測試資料輸出比 n 大的最小的Smith Number。
你可以假設這樣的數字存在。

Sample Input

3
6000
9980
4937774

Sample Output

6036
9985
4937775



解法
 github

窮舉法






判斷質數 function