Số Thứ K Chứa 666

Liệt kê theo thứ tự tăng dần tất cả các số nguyên dương có biểu diễn thập phân chứa chuỗi con liên tiếp $666$.

Với mỗi số thứ tự $k$, hãy in phần tử thứ $k$ của dãy này. Một số chỉ xuất hiện một lần trong dãy, kể cả khi nó chứa nhiều lần chuỗi $666$.

Input

• Dòng đầu chứa số nguyên $T$.
• Mỗi trong $T$ dòng tiếp theo chứa một số nguyên $k$.

Output

• Với mỗi truy vấn, in số thứ $k$ chứa $666$.

Constraints

• $1\le T\le 100$.
• $1\le k\le 10,000,000$.
• Đáp án nằm trong miền số nguyên không dấu $64$ bit.

Scoring

• Subtask $1$ ($50$ điểm): $T\le 10$ và $k\le 1,000$.
• Subtask $2$ ($50$ điểm): Không có giới hạn bổ sung.

Example

3
1
2
3

666
1666
2666