REPUNIT VER 2

Một repunit là một số nguyên dương chỉ chứa chữ số 1.

Hãy tìm số nguyên dương nhỏ thứ \(N\) mà có thể được phân tích thành tổng của \(3\) số repunit.

Input

• Một số nguyên dương \(T\) \((1 \le T \le 10^5)\)
• \(T\) dòng tiếp theo mỗi dòng là số nguyên dương \(N\) \((1 \le N \le 1000)\)

Output

• Mỗi dòng in ra đáp án.

Example

4 
 2 
 69 
 334 
 1000 

13 
 1122333 
 112222222333 
 111111111122222333

bài 1