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ụ

Input

50

Output

2

Giải thích

Có hai số thỏa yêu cầu đề bài là ~1~ và ~49~.