给定一个整数 $x$。你需要找到最小的非负整数 $y$，使得 $x$ 和 $y$ 的十进制表示中至少有一个共同的数字。

换句话说，存在某个十进制数字 $d$（$0 \le d \le 9$），它同时出现在 $x$ 的表示中和 $y$ 的表示中。

输入格式

• 第一行一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。
• 接下来 $t$ 行，每行一个整数 $x$（$1 \le x \le 1000$）。

输出格式

对每个测试用例输出一行一个整数 $y$，表示满足条件的最小非负整数。

为保证固定输出，本题答案本身唯一（最小值），无需额外固定规则。

样例

输入

5
6
96
78
122
696

输出

6
6
7
1
6