Định nghĩa: số \(ODD\) là số tự nhiên chỉ chứa các chữ số lẻ \((1, 3, 5, 7, 9)\).

Ví dụ: \(3, 19, 35, 197\) là các số \(ODD\). Còn \(21, 189, 23345\) không phải là số \(ODD\) vì có chứa chữ số chẵn.

Người ta viết liên tục các số \(ODD\) khởi đầu từ \(1\) thành một dãy số \(ODD\) vô tận: \(13579111315171931333537395153...\)

Yêu cầu: Tìm chữ số thứ \(k\) của dãy số \(ODD\) vô tận.

Input

• Một số nguyên dương \(k\).

Output

• Ghi ra chữ số thứ \(k\) của dãy số \(ODD\).

Constraints

• Subtask \(1\): \(40%\) số điểm với \(k≤10^5\).
• Subtask \(2\): \(30%\) số điểm với \(k≤10^7\).
• Subtask \(3\): \(30%\) số điểm với \(k≤10^{16}\).

Example

5

9

14

1