Một số nguyên dương được gọi là số đẹp nếu nó lớn hơn ~10~, mỗi chữ số của nó là số lẻ hoặc là số chính phương. Có nghĩa là mỗi chữ số của nó đều thuộc tập: ~\{0, 1, 3, 4, 5, 7, 9\}~ và tổng tất cả các chữ số của số đó chia hết cho ~3~.

Yêu cầu

Cho một số nguyên dương ~N~ ~(1 \le N \le 10^6)~. Hãy đếm có bao nhiêu số đẹp không vượt quá ~N~. Nếu không có ghi ~-1~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa số nguyên dương ~N~ ~(1 \le N \le 10^6)~.

Dữ liệu đầu ra

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

Ràng buộc dữ liệu

• Có 40% số test ứng với 40% số điểm của câu: ~1 \le N \le 10^3~;
• Có 30% số test ứng với 30% số điểm của câu: ~10^3 \le N \le 10^5~;
• Có 30% số test ứng với 30% số điểm của câu: ~10^5 \le N \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

100

OUTPUT

12