Một chuỗi số được tạo ra bằng cách thêm lần lượt các số có giá trị tăng dần vào chuỗi thoả mãn:

• Các số có ~1~ chữ số mà không chia hết cho ~2~.
• Các số có ~2~ chữ số mà không chia hết cho ~3~.
• Các số có ~3~ chữ số mà không chia hết cho ~4~.
• . . .
• Các số có ~i~ chữ số mà không chia hết cho ~i+1~.

Chuỗi số sẽ có dạng như sau: ~135791011131416171...~

Yêu cầu

Cho số nguyên dương ~n~, in ra chữ số thứ ~n~ của chuỗi số.

Input

• Một dòng duy nhất chứa số nguyên dương ~n~ ~(1≤n≤10^{15})~.

Output

Một dòng duy nhất là kết quả bài toán.

Sample Input

11

Sample Output

3

Subtask

• Có 50% số test ứng với 50% số điểm có ~1≤n≤10^6~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.