Dãy Chữ Số Ghép Khối

Xét một dãy vô hạn được tạo bằng cách ghép liên tiếp các "khối". Khối thứ $i$ là chuỗi thu được khi viết liền nhau tất cả các số nguyên dương từ $1$ đến $i$. Cụ thể:

• Khối thứ nhất: viết các số từ $1$ đến $1$, tức là "1".
• Khối thứ hai: viết các số từ $1$ đến $2$, tức là "12".
• Khối thứ ba: viết các số từ $1$ đến $3$, tức là "123".
• …
• Khối thứ $i$: viết 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ố vô hạn:

$$\text{“112123123412345…”}$$

$56$ chữ số đầu tiên của dãy là:

$$\text{“11212312341234512345612345671234567812345678912345678910”}$$

Các phần tử của dãy được đánh số bắt đầu từ $1$. Ví dụ, phần tử thứ $1$ là chữ số $1$, phần tử thứ $3$ là $2$, phần tử thứ $20$ là $5$, phần tử thứ $38$ là $2$, và phần tử thứ $56$ là $0$.

Bạn cần trả lời $q$ truy vấn độc lập. Trong truy vấn thứ $i$, cho một số nguyên $k_i$; hãy xác định chữ số nằm ở vị trí thứ $k_i$ 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_i$ — mô tả truy vấn tương ứng.

Dữ liệu ra

In ra $q$ dòng. Dòng thứ $i$ chứa một chữ số $x_i$ ($0\le x_i\le 9$) là phần tử ở vị trí thứ $k_i$ của dãy.

Ràng buộc

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

Ví dụ