Một ngày rảnh rỗi, Nam chơi trò chơi với những con số. Nam lấy một số tự nhiên \(N\) rồi thực hiện biến đổi thành số mới. Với mỗi cách biến đổi Nam xóa đi một số chữ số liên tiếp của \(N\) (nhưng không xóa hết) Nam nhận được một số mới, nếu số \(N\) được chia thành \(2\) phần thì số mới được ghép từ hai phần này và giữ nguyên thứ tự.

Yêu cầu: Hãy đếm các cách biến đổi như trên để số \(N\) mới sau khi biến đổi chia hết cho \(3\).

Lưu ý: Thao tác xóa tại hai vị trí khác nhau sẽ tạo ra hai cách biến đổi khác nhau. Số \(N\) giữ nguyên được coi là một cách biến đổi.

Input

• Vào từ file NDEL.INP chứa số nguyên dương \(N\) (\(N\) có không quá \(10^5\) chữ số).

Output

• Ghi ra file NDEL.OUT một số nguyên là số cách xóa tìm được.

Example

2001

4

160300

5

Scoring

• Subtask \(1\) (\(50\%\) số test): có số các chữ số của \(N \le 300\).
• Subtask \(2\) (\(25\%\) số test): có số các chữ số của \(N\le 10^4\).
• Subtask \(3\) (\(25\%\) số test): có số các chữ số của \(N \le 10^5\).