Xét cách biểu diễn số bởi các que diêm:

Với một số lượng que diêm cho trước, hãy xác định số nhỏ nhất và số lớn nhất mà bạn có thể biểu diễn được.

• Bạn không được để thừa que diêm nào.
• Số được biểu diễn không bắt đầu bởi chữ số ~0~.

Input

• Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ là số que diêm.

Giới hạn:

• ~1≤T≤38,2≤n≤39~

Output

• Với mỗi số ~n~ là số que diêm, in ra trên một dòng hai số nguyên dương là số nhỏ nhất và số lớn nhất mà ~n~ que diêm biểu diễn được, mỗi số cách nhau bởi một khoảng trắng.

Sample

Input #1

3
3
5
8

Output #1

7 7
2 71
10 1111

Problem source: Chuyên Sơn La Online Judge