Một số nguyên dương \(N\) được gọi là số đẹp nếu nó thỏa mãn các điều kiện sau:

• Số đó là số chính phương.
• Tổng các chữ số của nó là một số Fibonacci.

Yêu cầu: Cho số nguyên dương \(N\), đếm số lượng số đẹp nhỏ hơn hoặc bằng \(N\).

Dữ liệu

Vào từ file văn bản BNUM.INP một số nguyên dương \(N\).

Dữ liệu đảm bảo: \(1 \le N \le 10^9\).

Kết quả

Ghi vào file văn bản BNUM.OUT một số nguyên là số lượng số đẹp nhỏ hơn hoặc bằng \(N\).

Ràng buộc

• Subtask 1: \(60\%\) số test ứng với \(1 \le N \le 10^6\)
• Subtask 2: \(40\%\) số test không có ràng buộc gì thêm.

Ví dụ

50

2