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~ ~...~$$

(Hai số đầu tiên là ~1~ và ~3~, 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~ ~...~$$

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 ≤ 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 \le 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.

Sample Input

4

Sample Output

12