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

bài 1