Nhân ngày sinh nhật của Henry \((8/9/2050)\), cậu ấy đã được một người bạn của mình đố bài toán kì diệu như sau:

• Cho một dãy số nguyên dương được xác định như sau: \(a_0=p(p\in \mathbb{N}^{*})\) và \(a_i(i\ge 1)\) bằng tổng bình phương các chữ số của \(a_{i-1}\). Và dãy này chỉ dừng lại khi có một số đã xuất hiện trước đó !

Ví dụ:

• \(3\rightarrow 9 \rightarrow 81 \rightarrow 65 \rightarrow 61\rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow \text{...} \rightarrow 89\)
• Biết rằng: Với mọi \(p\in \mathbb{N}^{*}\) thì dãy đã cho luôn có tận cùng là \(1\) hoặc \(89\). (Quả là một điều kì diệu phải không nào !!!!)

Yêu cầu:

• Hỏi có bao nhiêu giá trị của \(p< N\) thỏa mãn dãy \(\left\{a_i\right\}\) có tận cùng là số \(89\).

Input:

• Một dòng duy nhất chứa số nguyên dương \(N(1\le N\le 10^5)\).

Output:

• In ra số lượng \(p\) thỏa mãn yêu cầu bài toán.

3

1