Bạn được cho một số nguyên x. Nhiệm vụ của bạn là tìm số nguyên không âm nhỏ nhất y sao cho các số x và y có ít nhất một chữ số chung. Nói cách khác, phải tồn tại một chữ số d xuất hiện trong cả cách biểu diễn của số x và số y.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 1000) — số lượng test case.
• Dòng đầu tiên của mỗi test case chứa một số nguyên x (1 ≤ x ≤ 1000).

Dữ liệu ra

Với mỗi test case, in ra một số nguyên y — số không âm nhỏ nhất thỏa mãn điều kiện.

Ví dụ

input
5
6
96
78
122
696


output
6
6
7
1
6

Giải thích

Trong test đầu tiên, số 6 và 6 có chữ số chung là 6. Không tồn tại số tự nhiên nhỏ hơn mà vẫn chia sẻ chữ số chung này.
Trong test thứ hai, số 6 và 96 có chữ số chung là 6.