UVA10042 Smith Numbers

1982 年，利哈伊大学的数学家阿尔伯特·威尔安斯基在浏览电话簿时，注意到他姐夫 H. 史密斯的电话号码具有以下奇特的性质：该号码各位数字之和等于其质因数各位数字之和。明白了吗？史密斯的电话号码是 $493-7775$ 。这个号码可以按其质因数的乘积形式写成如下方式： $$4937775=3*5*5*65827$$ 这个电话号码的所有数字之和为 $4+9+3+7+7+7+5=42$，而其质因数各位数字之和同样为 $3+5+5+6+5+8+3+7=42$。威尔安斯基对这一发现感到十分惊讶，于是将这类数以他姐夫的名字命名：**史密斯数** 。 由于这一观察结果对每个质数也同样适用，威尔安斯基后来决定，一个（简单且不复杂的）质数不值得成为史密斯数，于是他将质数排除在定义之外。 威尔安斯基在《两年制学院数学杂志》上发表了一篇关于史密斯数的文章，并能够列举出一系列不同的史密斯数：例如，$9985$ 是一个史密斯数，$6036$ 也是。然而，威尔安斯基未能给出一个比他姐夫电话号码更大的史密斯数。你的任务是找出比 $4937775$ 更大的史密斯数。

输入包含若干个数字. 第一行的整数 $T$ 代表以下数据的数量。 接下来 $T$ 行每行一个小于 $10^9$ 正整数 $n$ 。

对于每一个输入值 $n$，您需要计算出一个大于 $n$ 的最小“史密斯数”，并将每个数字打印在单独的一行上。数据保证这样的一个数是存在的。