Cho một xâu dài vô hạn chứa tất cả các số nguyên dương theo trình tự tăng dần:

\(12345678910111213141516171819202122232425 \ldots\)

Nhiệm vụ của bạn là xử lí \(q\) truy vấn trả lời cho câu hỏi: số nào nằm ở vị trí thứ \(k\) trong xâu?

Input

• Dòng đầu tiên chứa một số nguyên duy nhất \(q\): số lượng truy vấn.
• Sau đó gồm \(q\) dòng tiếp theo biểu diễn các truy vấn, mỗi dòng là một số nguyên \(k\): vị trí của kí tự cần tìm trong xâu (xâu được đánh số từ \(1\)).

Output

• Với mỗi truy vấn, in ra kết quả tương ứng trên từng dòng.

Constraints

• \(1 \le q \le 1000\)
• \(1 \le k \le 10^{18}\)

Example

Sample input

3
7
19
12

7
4
1