Hãy viết liên tiếp các số tự nhiên chia hết cho \(3\) (theo thứ tự tăng dần), và nối các số đó theo thứ tự lại thành một số mới:
\(3691215182124...\)

Hỏi: chữ số thứ \(N\) trong số ghép trên là số nào?

Input

• Một dòng duy nhất chứa một số tự nhiên \(N\) (\(1 \leq N \leq 10^{12}\))

Output

• Một số tự nhiên là chữ số thứ \(N\) trong số ghép được tạo ra.

Example

4

1

Scoring

• 60% số test ứng với 60% số điểm có \(N \leq 10^3\)
• 40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm