Cho số \(n\). Hãy tìm số lượng số có tổng bình phương các chữ số chia hết cho \(3\) nhỏ hơn \(n\)

Input

• Số nguyên dương \(n\)

Output

• Số lượng số tìm được

Điều kiện

• \(1 \le n \le 10^{10000}\)

Sample Input 1

9

Sample Output 1

3

Sample Input 2

10

Sample Output 2

4