Nhân đang tập đếm các số \(1, 2, 3, 4, 5, \dots\) Nhận thấy việc này quá dễ, cộng với việc vừa mới học được phép nhân, Nhân quyết định đếm các số chính phương (là những số bằng một số nguyên nhân với chính nó) và viết chúng ra giấy và thu được một dãy dài có các số đầu tiên là \(149162536\dots\) Nhân muốn biết chữ số thứ \(n\) của dãy là bao nhiêu. Các bạn hãy tính giúp Nhân nhé.

Input

• Một số nguyên dương duy nhất \(n\) (\(1 \le n \le 10^{18}\)).

Output

• Chữ số thứ \(n\) của dãy.

Example

10

4

Subtask

• Subtask 1 (\(30\%\) số điểm): \(n \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^{12}\).
• Subtask 3 (\(40\%\) số điểm): Không có giới hạn gì thêm.