Số gần chính phương

Một số tự nhiên được gọi là “Số gần chính phương” nếu số đó thỏa mãn đồng thời ba điều kiện sau:

• Có từ 3 chữ số trở lên.
• Chữ số ở hàng cao nhất (hàng đầu tiên bên trái) là một số chính phương.
• Tổng của hai chữ số cuối cùng (hàng chục và hàng đơn vị) là một số chính phương.

Yêu cầu: Cho số nguyên dương $M$, hãy đếm xem có bao nhiêu số “Số gần chính phương” trong đoạn từ 1 đến $M$.

Trong tệp GCP.INP gồm một số nguyên dương $M$.

Đưa ra tệp GCP.OUT gồm một số nguyên duy nhất là số lượng số “Số gần chính phương” tìm được.

• Subtask 1: 50% số test có $100 \le M \le 999$;
• Subtask 2: 25% số test M có $1000 \le M \le 10^6$;
• Subtask 3: 25% số test M có dạng $10^K$ với $6 < K < 18$.