初级启示者
4147 最大可被3除的数字
题目描述 Description
酷町猫喜欢被3整除的数字。他有一个巨大的数字s。酷町猫想从中裁出最多可被3整除的数字。为了做到这一点，他在相邻数字对之间进行任意数量的垂直切割。因此，在m次这样的切割之后，总共会有m+1个零件。酷町猫分析得到的每一个数字，找出那些可以被3整除的数字。例如，如果原来的数字是s=3121，那么酷町猫可以用两个切口将其切割成三部分：3 | 1 | 21。结果，他会得到两个可以被3整除的数字。
酷町猫可以进行任意数量的垂直切割，每个切割都在一对相邻数字之间进行。生成的数字不能包含额外的前导零（即，如果且仅当该数字正好是一个字符“0”时，该数字可以以0开头）。例如，007、01和00099不是有效数字，但90、0和10001有效。
请问，酷町猫能得到的最大可被3除的数字是多少？
输入描述 Input Description
一行，包含一个正整数S。数字S的位数在1到2*10^5之间（含1和2）。第一个（最左边）数字不等于0。
输出描述 Output Description
输出酷町猫在给定数字s上进行垂直切割所能得到的最大可被3除的数字有多少个。
样例输入 Sample Input
【输入样例1】 3121 【输入样例2】 6 【输入样例3】 1000000000000000000000000000000000 【输入样例4】 201920181
样例输出 Sample Output
【输出样例1】 2 【输出样例2】 1 【输出样例3】 33 【输出样例4】 4
数据范围及提示 Data Size & Hint
在第一个示例中，数字上的最佳切割示例集是3 | 1 | 21。
在第二个示例中，您不需要进行任何切割。指定的数字6构成一个可被3整除的数字。
第三个示例中，必须在每对数字之间进行切割。因此，Polycarp得到一位数字1和33位数字0。33位数字0中的每一位都构成一个可被3整除的数字。
在第四个示例中，最佳切割的示例集是 2 | 0 | 1 | 9 | 201 | 81。数字0、9、201和81可以被3整除。
