Ta gọi số nguyên dương K là một số BDN nếu các chữ số trong K chỉ bao gồm các 0 hoặc 1 có nghĩa. Ví dụ số K = 101 là số BDN, k=102 không phải là số BDN. Số BDN của N là số P = M' N sao cho P là số BDN. Cho số tự nhiên N, hãy tìm số BDN nhỏ nhất của N. Ví dụ. Với N = 2, ta tìm được số BDN của N là P = 5'2 = 10. N = 17 ta tìm được số BDN của 17 là P = 653'17=11101.

Định dạng đầu vào: Dòng đầu tiên ghi lại số tự nhiên T là số lượng Test; T dòng kế tiếp mỗi dòng ghi lại một bộ Test. Mỗi test là một số tự nhiên N.

Ràng buộc: 1<=T<=100; 1<=N<=500;

Đầu ra: Đưa ra kết quả mỗi test theo từng dòng.

Input:

14
19
18
9
10
27
23
14
22
40
38
6
13
30
43

Output:

11001
1111111110
111111111
10
1101111111
110101
10010
110
1000
110010
1110
1001
1110
1101101