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 FNUM.INP có cấu trúc:

• Dòng 1 chứa một số nguyên dương \(N(1≤N≤10^9).\)

Kết quả ghi vào file văn bản FNUM.OUT có cấu trúc:

• Ghi 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≤N≤10^6\)

• Subtask 2: 40% số test không có ràng buộc gì thêm.

Sample Input

50

Sample Output

2