Một số tự nhiên được cho là Số Tiến Đạt nếu nó chỉ chứa các số 0 và số 9.

Nhiệm vụ của bạn là tìm số Tiến Đạt nhỏ nhất chia hết cho số nguyên dương n cho trước.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test t (t ≤ 10⁴).

Mỗi dòng trong t dòng tiếp theo chứa một số nguyên dương n (n ≤ 500).

Kết quả

Với mỗi test, in ra số Tiến Đạt nhỏ nhất chia hết cho n (đáp án đảm bảo có nhiều nhất 13 chữ số).

Ví dụ

Input:
3
5
7
1

Output:
90
9009
9