Chữ số trong dãy khối

Xét một dãy vô hạn được tạo thành từ các khối liên tiếp. Khối thứ $i$ là dãy các số nguyên dương từ $1$ đến $i$ viết liền nhau. Cụ thể:

• Khối thứ $1$ gồm các số từ $1$ đến $1$.
• Khối thứ $2$ gồm các số từ $1$ đến $2$.
• Khối thứ $3$ gồm các số từ $1$ đến $3$.
• ...
• Khối thứ $i$ gồm các số từ $1$ đến $i$.

Ghép tất cả các khối lại theo thứ tự, ta được dãy chữ số:

$$112123123412345\dots$$

Ví dụ, $56$ phần tử đầu tiên của dãy là:

$$11212312341234512345612345671234567812345678912345678910$$

Các phần tử của dãy được đánh số từ $1$. Chẳng hạn, phần tử thứ $1$ là $1$, phần tử thứ $3$ là $2$, phần tử thứ $20$ là $5$, phần tử thứ $38$ là $2$, phần tử thứ $56$ là $0$.

Cho $q$ truy vấn độc lập. Với mỗi truy vấn cho một số nguyên $k$, hãy tìm chữ số đứng ở vị trí thứ $k$ của dãy.

Dữ liệu vào

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

Dữ liệu ra

In ra $q$ dòng. Dòng thứ $i$ chứa một chữ số duy nhất, là chữ số ở vị trí $k$ của truy vấn thứ $i$.

Ràng buộc

• $1\le q\le 500$
• $1\le k\le {10}^{18}$

Ví dụ