题目描述

一个十进制正整数 $n$，可以从 $n$ 中截取很多种不同的子串，如果这个子串构成的数是 $3$ 的倍数，这个字串称为三倍子串。

例如：当 $n=1234$ 时，有且仅有 $3$，$12$，$123$，$234$ 这四个子串是 $3$ 的倍数。

桐桐很厉害，她能马上求出答案，你也一起算算吧。

输入格式

单个整数：表示输入的数 $n$ 。

数据范围

10% 的数据，$1\le n$ 的位数 $\le 19$;

100%的数据，$20 \le n$ 的位数 $\le 10^7$。

输出格式

单个整数：表示 $3$ 的倍数的子串数量。

样例

95764

6

1111

2

样例 1 解释

子串 $6$,$9$,$57$,$576$,$957$,$9576$是 $3$ 的倍数

样例 2 解释

有两个 $111$ 都是 $3$ 的倍数