Truy Vấn Chữ Số

Xét xâu vô hạn được tạo bằng cách ghép tất cả các số nguyên dương theo thứ tự tăng dần:

• $$\underset{1}{\underbrace{1}}\underset{2}{\underbrace{2}}\underset{3}{\underbrace{3}}\cdots \underset{9}{\underbrace{9}}\underset{10}{\underbrace{1}}\underset{11}{\underbrace{0}}\underset{12}{\underbrace{1}}\underset{13}{\underbrace{1}}\underset{14}{\underbrace{1}}\underset{15}{\underbrace{2}}\cdots$$

Cho $q$ truy vấn, mỗi truy vấn hỏi: chữ số ở vị trí thứ $k$ (đánh số từ 1) trong xâu trên là gì?

Dữ liệu vào

Dòng đầu là số nguyên $q$.

• $q$ dòng tiếp theo, mỗi dòng là một số nguyên $k$.

Dữ liệu ra

Với mỗi truy vấn, in ra chữ số tại vị trí $k$.

Ràng buộc

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

Ví dụ