Một ngày vov đố hbl nếu \(67\) người AC thì vov sẽ làm người yêu của hbl nghe vậy hbl từ lâu đã thích vov nên đã đồng ý ngay \(:\)
Dãy số có Quy luật như sau \(:\)
\(5, 11, 28, 53, 126, 175, 296, 369, 538, 851, 972, 1381, 1694, 1863, 2224, 2825, 3498, 3739, 4508, 5061, ...\)
Hãy AC bài tập để đẩy thuyền vov và hbl nhé mọi người ^^!

Yêu cầu

Tìm số thứ \(N\) của dãy số.

Input

• Số nguyên dương \(N\) \((1 \le N \le 10^7)\)

Output

• Một số nguyên dương là số thứ \(N\) của dãy số .

Example

5

126

10

851

Scoring

• Subtask \(1\): \(20\%\) \((1 \le N \le 100)\).
• Subtask \(2\): \(30\%\) \((1 \le N \le 10^5)\).
• Subtask \(3\): \(50\%\) Không còn ràng buộc gì thêm.