Số Fibonacci được định nghĩa là: \(F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}\) với mọi \(n > 1\).

Cho xâu \(S\) có độ dài không vượt quá \(10^6\) gồm các kí tự chữ cái và kí tự chữ số. Các số trong xâu \(S\) là một dãy các kí tự chữ số liên tiếp được phân tách bởi các kí tự chữ cái.

Sau khi thực hiện lấy ra các số trong \(S\), ta thu được một dãy số \(A\) gồm \(m\) số nguyên dương \(a_1, a_2, \dots, a_m\). Ví dụ, xâu \(S =\) ab123cd67e15g67, ta có dãy số \(A = [123, 67, 15, 67]\). Chú ý rằng các số \(1, 12, 2, 23, 3, 6, 7, 1, 5\) không được tính là tồn tại trong dãy \(A\).

Yêu cầu: Cho biết tất cả các phần tử trong dãy \(A\) luôn có giá trị không vượt quá \(10^{18}\). Hãy đếm số lượng phần tử trong dãy \(A\) là số Fibonacci.

Input

• Một dòng duy nhất chứa xâu \(S\) có độ dài không vượt quá \(10^6\).

Output

• Một số nguyên duy nhất là số lượng phần tử trong dãy \(A\) là số Fibonacci.

Example

ab14def2cd1ag6bc2h13

4

Scoring

• Subtask \(1\) (\(0.5\) điểm): Các số trong dãy \(A\) đều có \(1\) chữ số.
• Subtask \(2\) (\(0.4\) điểm): Các số trong dãy \(A\) có \(1\) hoặc \(2\) chữ số.
• Subtask \(3\) (\(1.1\) điểm): Không có ràng buộc bổ sung.