Xét một xâu dài vô hạn gồm các số tự nhiên liên tiếp viết liền nhau như sau:

~123456789101112131415161718192021222324252627...~

Nhiệm vụ của bạn là trả lời ~q~ truy vấn có dạng: chữ số thứ ~k~ của xâu là gì?

Input:

Dòng đầu tiên là số ~q~: số truy vấn ~(1 ≤ q ≤ 1000)~

~q~ dòng tiếp theo, mỗi dòng chứa một số ~k~ ~(1 ≤ k ≤ 10~^~18~~)~. Lưu ý: chỉ số của xâu được tính từ ~1~

Ví dụ:

Input

3
7
19
12

Output

7
4
1