相同数字

给定一个整数 x，你需要找出最小的非负整数 y，使得数字 x 和 y 至少有一个相同的数位数字。换句话说，必须存在一个十进制数字 d，它同时出现在数字 x 和数字 y 的表示中。

输入

第一行包含一个整数 t（1 ≤ t ≤ 1000）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 x（1 ≤ x ≤ 1000）。

输出

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

示例

输入

5
6
96
78
122
696

输出

6
6
7
1
6

note

当x=696时，符合条件的y有6,9,69,96,696 当x=122时，符合条件的y有1,2,12,22,122