Đặ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~

~u_{19}=1234567891234567891~

~u_{20}=12345678912345678912~

...

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...)~

Ví dụ Với ~n=16~ thì thì số thứ 16 trong ~S~ là số ~1~ nên kết quả ra số ~1~

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

• Một dòng thứ nhất chứa số ~n\ (1\le n\le 10^9)~

Output

• In ra đáp án cần tìm

Example

Input

10

Output

4

Scoring

• ~60\%~ : ~1\le n\le 1000000~
• ~40\%~ : Không có điều kiện gì