Viết liền các số nguyên dương liên tiếp, từ nhỏ đến lớn, bắt đầu từ ~1~, ta sẽ được một dãy dài vô hạn gồm các chữ số: ~123456789101112131415161718192021222324252627282930313233343536\ldots~

Bạn được cho số nguyên dương ~k~, nhiệm vụ của bạn là tìm chữ số thứ ~k~ của dãy trên.

Input

• Dòng thứ nhất chứa số nguyên dương ~T~ - số bộ dữ liệu. (~T \leq 10^3~)
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~.

Output

• In ra ~T~ dòng, mỗi dòng chứa một chữ số cho bộ dữ liệu tương ứng.

Subtasks

• Subtask 1 (~20\%~ số điểm): Mọi số ~k \leq 50~.
• Subtask 2 (~30\%~ số điểm): Mọi số ~k \leq 10^6~.
• Subtask 3 (~50\%~ số điểm): Mọi số ~k \leq 10^{18}~.

Sample Test

Input

5
8
18
16
14
19

Output

8
1
1
1
4