Hôm nay, cô giáo giảng cho cả lớp về dãy số Fibonacci. Boast nghĩ rằng mình đã làm tất cả các dạng bài liên quan đến dãy số này rồi nên không tập trung, làm ồn ảnh hưởng đến các bạn khác.

Cô giáo liền giao cho bạn ấy một vấn đề như sau, phải làm xong, làm đúng thì mới được về nhà: Hãy đếm số lượng số chẵn có trong ~N~ số đầu tiên của dãy:

$$1, 1, 2, 3, 5, 8 , 13, 21, ...$$

Vì ~N~ quá lớn, Boast mới đếm được đến ~10^7~ thì đã bị TLE (Time Limit Exceeded). Trời thì đã tối, Boast đói hoa hết cả mắt. Bạn ấy đã biết lỗi của mình rồi. Là các coder tốt bụng, các bạn hãy giúp Boast AC (Accepted) nhé!

Input Specification

• Một dòng chứa số nguyên ~N~ ~(1 \le N \le 10^{15})~

Output Specification

• Một dòng chứa một số nguyên là kết quả bài toán.

Sample Input 1

5

Sample Output 1

1