Max 想买一块新滑板。他计算了购买一块新滑板需要多少钱。他把计算器落在地板上,然后去向父母要钱。与此同时,他的弟弟优素福来了,开始胡乱按键。不幸的是,麦克斯忘记了他计算的数字。他唯一知道的是这个数字可以被4整除。
给你一个由数字组成的字符串 s (Yusuf 随机按键后计算器显示屏上的数字)。您的任务是找到可被 4 整除的子字符串的数量。子字符串可以以零开头。
字符串的子字符串是连续字符的非空序列。
例如,如果字符串 s 是 124,那么我们有四个可被 4 整除的子字符串:12、4、24 和 124。对于字符串 04,答案是 3:0、4、04。
由于输入/输出可能达到巨大的尺寸,建议使用快速输入/输出方法:例如,在 C++ 中更喜欢使用 gets/scanf/printf 而不是 getline/cin/cout,在 Java 中更喜欢使用 BufferedReader/PrintWriter 而不是 Scanner/System.out。
输入
唯一一行包含字符串 s (1 ≤ |s| ≤ 3·105)。字符串 s 仅包含 0 到 9 之间的数字。
输出
打印整数 a — 字符串 s 中能被 4 整除的子串的数量。
请注意,答案可能很大,因此您应该使用 64 位整数类型来存储它。在 C++ 中,您可以使用 long long 整型,在 Java 中,您可以使用 long 整型。
示例
输入 #1
124
输出 #1
4
输入 #2
04
输出 #2
3
输入 #3
5810438174
输出 #3
9