题目背景

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

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

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

题目描述

给定的一系列正整数，对于每个正整数，计算其最小生成元。

输入格式

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

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

输出格式

$N$ 个非负整数，依次是输入的每个正整数的最小生成元。如果输入的正整数没有生成元，此时直接输出 $0$。

输入输出样例

5
216 64 2005 101 214

198 0 1979 91 197

说明/提示

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