Đổi số

Sau khi chơi trò xếp que tính, em Xốp chuyển qua chơi trò đổi số. Cho em Xốp một số nguyên dương \(N\). Em Xốp có quyền thay đổi một chữ số bất kỳ của số này để tạo thành số mới.

Với yêu cầu số mới tạo ra không được chứa chữ số \(0\) ở đầu, phải khác số ban đầu và chia hết cho \(3\).

Input

Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 10^{18}\)).

Output

In ra một số nguyên duy nhất là số lượng các số khác nhau mà em Xốp có thể tạo ra theo yêu cầu đề bài.

Scoring

• Có 30% số điểm ứng với \(N \le 1000\).
• 70% số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

13

Sample Output 1

6

Sample Input 2

5

Sample Output 2

3

Notes

Với \(N=13\), các số có thể tạo ra là \(12, 15, 18, 33, 63, 93\). Tất cả các số này đều khác \(13\), không có \(0\) ở đầu và chia hết cho \(3\).