Mô tả bài toán:

Cho một chuỗi vô hạn chứa tất cả các số nguyên dương theo thứ tự tăng dần:
12345678910111213141516171819202122232425...

Nhiệm vụ của bạn là xử lý ~ q ~ truy vấn. Mỗi truy vấn yêu cầu xác định chữ số tại vị trí ~ k ~ trong chuỗi.

Input:

• Dòng đầu tiên chứa một số nguyên ~ q ~: số lượng truy vấn.
• ~ q ~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~ k ~: vị trí cần tìm trong chuỗi.

Output:

• Với mỗi truy vấn, in ra chữ số tương ứng tại vị trí ~ k ~.

Ràng buộc:

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

Ví dụ:

Input:

3
7
19
12

Output:

7
4
1

Giải thích:

• Chuỗi là: 123456789101112...
  • Vị trí 7: Chữ số 7.
  • Vị trí 19: Chữ số 4 (từ số 14).
  • Vị trí 12: Chữ số 1 (từ số 10).