Viết liên tiếp các số nguyên dương theo thứ tự tăng dần để tạo thành một chuỗi chữ số vô hạn:

123456789101112131415161718192021...

Có ~q~ câu hỏi độc lập. Mỗi câu hỏi cho một vị trí ~k~ được đánh số từ 1 trong chuỗi trên.

Hãy xác định chữ số nằm tại vị trí ~k~ cho từng câu hỏi.

Input

• Dòng đầu gồm số nguyên ~q~, là số câu hỏi.
• Mỗi trong ~q~ dòng tiếp theo gồm một số nguyên ~k~, là vị trí cần tìm trong chuỗi vô hạn và được đánh số từ 1.

Output

• Với mỗi câu hỏi, in trên một dòng chữ số nằm tại vị trí ~k~ tương ứng.

Giới hạn

• ~1 ≤ q ≤ 1000~.
• ~1 ≤ k ≤ 10^{18}~.

Ví dụ

Input

3
7
19
12

Output

7
4
1

Giải thích ví dụ

Vị trí 7 chứa chữ số 7. Sau 9 chữ số đầu, các số có hai chữ số bắt đầu từ 10; vị trí 19 rơi vào chữ số cuối của số 14, nên kết quả là 4. Vị trí 12 là chữ số đầu của số 11, nên kết quả là 1.