Dãy chữ số

Cho dãy số vô hạn \(1121231234123451234561234567\)........ Khối thứ nhất chứa số \(1\), khối thứ \(2\) chứa số \(1\) đến \(2\), khối thứ \(3\) chứa số từ \(1\) đến \(3\), .... , khối thứ \(i\) chứa các số từ \(1\) đến \(i\).

56 kí tự đầu tiên là

"\(11212312341234512345612345671234567812345678912345678910\)". Các kí tự được đánh số từ \(1\) trở đi. Ví dụ, kí tự thứ \(1\) là \(1\), kí tự thứ \(3\) là 2, kí tự thứ \(56\) là \(0\).

Cho \(Q\) truy vấn, truy vấn thứ \(i\) gồm một số nguyên dương \(k\). In ra kí tự thứ \(k\) trong dãy số.

Input

Dòng đầu tiên là số nguyên dương \(Q (1 <= Q <= 500)\)

\(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k\).

Output

\(Q\) dòng, dòng thứ \(i\) là kết quả của truy vấn thứ \(i\).

Example

5
1
3
20
38
56

1
2
5
2
0

Scoring

\(25\%\) số test có \(k <= 10^3\)

\(25\%\) số test có \(k <= 10^6\)

\(25\%\) số test có \(k <= 10^9\)

\(25\%\) số test có \(k <= 10^18\)