THỰC HÀNH

Xét cách biểu diễn số bởi các que diêm (mỗi gạch là một 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.

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.

Example

Input:
3
3
5
8
Output:
7 7
2 71
10 1111

Giới hạn: 1 ≤ T ≤ 10, 2 ≤ n ≤ 40