Một số nguyên dương ~N~ được gọi là số đẹp nếu 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 đầu vào

Gồm một số nguyên dương ~N~ ~(1 \le N \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng số đẹp nhỏ hơn hoặc bằng ~N~.

Ràng buộc dữ liệu

• Có 60% số test của bài thỏa mãn ~N \le 10^6~.
• Có 40% số test của bài không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

50

OUTPUT

2

Giải thích: Có ~2~ số thỏa yêu cầu đề bài là ~1~ và ~49~.