Khang là một cậu con trai nhà giàu, học giỏi, được nhiều cô gái theo đuổi. Thế nhưng đáng tiếc cho những cô gái ấy khi Khang đã có "nóc nhà". Quen nhau không được bao lâu thì anh ta và "nóc nhà" ấy "đường ai nấy đi". Càng xui xẻo hơn cho Khang khi sau đó cô gái ấy đã hack account facebook của anh. Cảm thấy thế giới này toàn là những điều dối trá, anh ta đã tìm đến mạng xã hội Fake Social của vị cựu tổng thống nào đó. Nhưng cơ chế kích hoạt của mạng xã hội này vô cùng phức tạp, bởi chủ của nó là một người thích “make it complicated”. Khang vì mới chia tay nên đầu óc không còn minh mẫn nữa. Biết bạn là một người rất thông minh, hãy giúp Khang kích hoạt tài khoản mạng xã hội để khám phá Fake Social nhé. Mã kích hoạt là đáp án của bài toán sau:

Cho \(A\) là tập hợp các số nguyên không âm không lớn hơn \(n\), đôi một phân biệt, thỏa mãn tích \(2\) số bất kì thuộc \(A\) đều là số chính phương. Hỏi tập \(A\) có tối đa bao nhiêu phần tử.

Input

• Một dòng duy nhất chứa số nguyên \(n\).

Output

• Một dòng duy nhất là kết quả của bài toán.

Ràng buộc

• Subtask 1 (\(20\%\) số điểm): \(n \le 20\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^{18}\).
• Subtask 3 (\(50\%\) số điểm): \(n \le 10^{100}\).

8

2

Giải thích

• Số phần tử lớn nhất có thể của tập hợp \(A\) là \(2\). Khi đó \(A\)={\(2\), \(8\)}