Hằng năm, vào ngày mùng 10 tháng 3 âm lịch — ngày lễ Giỗ Tổ Hùng Vương, người dân cả nước lại cùng nhau trở về Khu di tích lịch sử Đền Hùng, tọa lạc trên quần thể núi Nghĩa Lĩnh linh thiêng, thuộc tỉnh Phú Thọ để dâng hương tưởng nhớ các vua Hùng Vương và bày tỏ lòng biết ơn tổ tiên.

Dù ai đi ngược về xuôi, nhớ ngày Giỗ Tổ mùng mười tháng ba.

Không chỉ là dịp tưởng nhớ cội nguồn dân tộc, đây còn là một lễ hội lớn mang đậm bản sắc văn hóa Việt Nam, nơi diễn ra nhiều hoạt động văn hóa truyền thống và trò chơi dân gian. Trong không khí trang nghiêm mà vẫn rộn ràng ấy, hàng vạn người từ khắp mọi miền đất nước cùng hội tụ, tạo nên sự gắn kết bền chặt trong tinh thần đoàn kết và sẻ chia.

Trong lễ hội năm nay có một trò chơi rất thú vị, thu hút đông đảo người tham gia.

Quản trò viết lên bảng một dãy số chỉ gồm các chữ số lẻ mà ông yêu thích: \(1, 3, 5, 7, 9\).
Sau đó, ông tiết lộ một phần của dãy số bí ẩn: \(5, 7, 1, 7, 7, 3, 9, 1, 9, 9, 7, 5,\dots\)

Ông nói:

“Dãy số này tuân theo một quy luật rất đơn giản.
Ai tìm được số thứ n, người đó sẽ chiến thắng.”

Yêu cầu

Cho số nguyên dương n, hãy tìm giá trị của số hạng thứ n của dãy.

Input

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

Output

• In ra một chữ số là số hạng thứ \(n\) của dãy tìm được.

Example

1

5

50

9

100

3

Constraints

• Nhóm 1 (50% số điểm) : \(n \le 10^{6}\).
• Nhóm 2 (50% số điểm) : \(n \le 10^{18}\).