Cho dãy số \(A\) có quy luật như sau: \(1, 3, 2, 6, 4, 12, 8, 24, 16, 48, 32, 96, 64, 192, 128 \ldots\) (số ở vị trí thứ \(i\) bằng hai lần số ở vị trí thứ \(i - 2\)).

Lấy hai chữ số cuối cùng của các số của dãy số \(A\) ta được dãy số \(B\):

\(1, 3, 2, 6, 4, 12, 8, 24, 16, 48, 32, 96, 64, 92, 28 \ldots\)

Cho số tự nhiên \(N\). Tính tổng \(N\) số đầu tiên của dãy số \(B\).

Input

• Gồm một dòng chứa một số tự nhiên \(N\) \((N \leq 10^{12})\).

Output

• Gồm một dòng, chứa một số tự nhiên là kết quả của bài toán.

Scoring

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

Example

4

12