Khi viết các số tự nhiên tăng dần từ ~1, 2, 3,…~ liên tiếp nhau, ta nhận được một dãy các chữ số thập phân vô hạn.

Ví dụ: ~1234567891011121314151617181920...~

Input

• Gồm ~N~ dòng (~N~ không biết trước), mỗi dòng ghi một số nguyên dương ~K (1 \le K \le 10^9)~.

Output

• Gồm ~N~ dòng, mỗi dòng ghi 1 chữ số duy nhất là chữ số thứ ~K~ trong dãy vô hạn các chữ số thập phân đã nói trên.

Sample

Input #1

5
10
54

Output #1

5
1
3