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

Constraints

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

Output

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

Example

3
7
19
12

7
4
1