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…\)

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

• Subtask \(1(40\%\) số điểm): \(Q=1,k \leq 10^6\)
• Subtask \(2(60\%\) số điểm): \(Q\leq 10^3, k \leq 10^{18}\)

3
7
19
12

7
4
1