Đặt:

\(u_1=1\)

\(u_2=12\)

\(u_3=123\)

\(u_4=1234\)

...

\(u_9=123456789\)

\(u_{10}=1234567891\)

\(u_{11}=12345678912\)

...

\(u_{18}=123456789123456789\)

...

Gọi \(S\) là xâu được tạo ra bằng cách nối liên tiếp các xâu \(u_1,u_2,u_3,...\) (Độ dài của xâu \(S\) là vô tận)

\((S=112123123412345123456...)\)

Yêu cầu: Cho trước số nguyên dương \(n\). Hãy in ra kí tự thứ \(n\) của xâu \(S\) (biết rằng, xâu \(S\) được đánh chỉ số bằng đầu từ \(1\))

Input:

• Dòng thứ nhất chứa số \(t(1\le t\le 1000)\) - Thể hiện số lượng testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa số \(n(1\le n\le 10^9)\)

Output:

• Ứng với mỗi testcase, in ra đáp án cần tìm

Ví dụ:

Input 1:

4
1
2
3
10

Output:

1
1
2
4

Subtask:

• \(20\text{%}\) : \(1\le n\le 30\)

• \(80\text{%}%\) : Không có điều kiện gì