题目背景

如果正整数 $x$ 加上 $x$ 各位上数字之和得到 $y$，就称 $x$ 是 $y$ 的生成元，或者说 $y$ 的生成元是 $x$。

一个正整数的生成元可能不唯一，例如 $101$ 就有 $100$ 和 $91$ 两个生成元。

有些正整数没有生成元，例如 $1,3,5,7,9,20,31,42,53,64,75,86,97,...$ 这些正整数都没有生成元。

对于正整数 $k_0$，如果计算得到其生成元是 $k_1$，继续计算得到 $k_1$ 的生成元 $k_2$，继续计算得到 $k_2$ 的生成元 $k_3$，……，这样持续溯源，最后得到一个生成元 $k_i$ 并且 $k_i$ 没有生成元，到这里溯源过程结束，最后的生成元 $k_i$ 就是溯源得到的原始生成元。因为一个正整数的生成元可能不唯一，所以这样的溯源可能有多种方式，现在要计算所有溯源方式得到的所有原始生成元的最小值。

例如整数 $101$ 有以下两种溯源方式：

1. $101←100←86$，原始生成元是 $86$；
2. $101←91←77←70←62←49←38←28←23←16←8←4←2←1$，原始生成元是 $1$。

可知整数 $101$ 的所有溯源方式得到的所有原始生成元的最小值是 $1$。

例如整数 $214$ 有以下六种溯源方式（书写时省略了一些中间溯源过程）：

1. $214←197←184←173←163←149←142←134←130←119←109←95←...←5$，原始生成元是 $5$；
2. $214←197←184←173←163←149←142←134←130←119←109←104←...←20$，原始生成元是 $20$；
3. $214←206←193←...←143$，原始生成元是 $143$；
4. $214←206←202←191←181←167←160←152←139←128←118←113←97$，原始生成元是 $97$；
5. $214←206←202←191←181←167←160←152←139←128←118←113←106←...←31$，原始生成元是 $31$；
6. $214←206←202←200←190←176$，原始生成元是 $176$。

可知整数 $214$ 的所有溯源方式得到的所有原始生成元的最小值是 $5$。

题目描述

给定的一系列正整数，对于每个正整数，计算其所有溯源方式得到的所有原始生成元的最小值。

输入格式

输入文件名：gen.in

第 $1$ 行是一个正整数 $N$。

第 $2$ 行有 $N$ 个正整数 $n_i$（$1\leq i \leq N$），整数间用一个空格隔开。

输出格式

输出文件名：gen.out

$N$ 个非负整数，依次是输入的每个正整数的所有溯源方式得到的所有原始生成元的最小值。如果输入的正整数没有生成元，则无法溯源，此时直接输出 $0$。

输入输出样例

注意本题要重定向输入输出到指定文件

5
216 64 2005 101 214

9 0 1862 1 5

说明/提示

注意本题要重定向输入输出到指定文件

👀️ 对于$100\%$ 的数据，$N\leq 1000$，$1 \leq n_i \leq 10^5$。