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\).

Input

• \(t(t \le 10^4)\) - số test
• Mỗi test \(1\) số nguyên dương \(n(n \le 500)\)

Output

• 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ố).

Example

3
5
7
1 

90
9009
9