给定一个由数字组成的字符串 $s$，请你计算能够被 $4$ 整除的 $s$ 的子串数量。

子串可以包含前导 $0$。

例如，如果 $s$ 为 124，则满足条件的子串有 $4$ 个：12，4，24，124；如果 $s$ 为 04，则满足条件的子串有 $3$ 个：0，4，04。

输入格式

一个由数字组成的字符串 $s$。

输出格式

一个整数，表示满足条件的子串数量。

数据范围

前 $4$ 个测试点满足 $1 \le |s| \le 10$。
所有测试点满足 $1 \le |s| \le 3 \times 10^5$。

输入样例1：

124

输出样例1：

4

输入样例2：

04

输出样例2：

3

输入样例3：

5810438174

输出样例3：

9