Xét một số nguyên dương ~x~.

Gọi ~f(x)~ là tích các chữ số của ~x~ và ~g(x)~ là tổng các chữ số của ~x~. Khi đó số ~x~ được gọi là đẹp nếu ~f(x) \ne 0~ và ~f(x)~ chia hết cho ~g(x)~.

Cho một số nguyên dương ~n~, hãy tìm một số ~x~ đẹp có ~n~ chữ số.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ (~1 \le T \le 10^6~) — số lượng bộ test.

~T~ dòng sau, mỗi dòng chứa một số nguyên dương ~n~ (~1 \le n \le 5 \cdot 10^6~) — số lượng chữ số của số cần tìm.

Gọi ~N~ là tổng ~n~ trong tất cả mọi test. Dữ liệu đảm bảo ~N~ không vượt quá ~5 \cdot 10^6~.

Output

Với mỗi test, in ra một số đẹp gồm ~n~ chữ số.

Scoring

Sample Input 1

6
1
2
3
4
3
4

Sample Output 1

9
63
167
6666
761
3789