Cho xâu \(S\) gồm các chữ số. Hãy đếm số lượng xâu con \([l \dots r]\) sao cho tạo thành một số tự nhiên chia hết cho \(3\) (không có số \(0\) đứng đầu)

Dấu hiệu chia hết cho \(3\): Một số chia hết cho \(3\) khi tổng các chữ số của số đó chia hết cho \(3\). Ví dụ: \(354\) chia hết cho \(3\) vì \(3 + 5 + 4 = 12\) chia hết cho \(3\).

Input

• Gồm dòng duy nhất chứa xâu \(S\) \((|S| \leq 10^5)\).

Output

• Gồm một số nguyên duy nhất là số xâu con thỏa mãn.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(|S| \leq 5000\)
• Subtask \(2\) (\(50\%\) số điểm): \(|S| \leq 10^5\)

Example

363

6