问题 3929 --植树节B

3929: 植树节B

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

植树节那天每个班级都要挂出宣传标语,学校要对每个班级的宣传标语进行打分,得到的分数就是该标语里含有子序列“312”的个数(其中3,1,2三个数字允许不相邻但一定要按照该顺序),例如,给定序列33122,那么得分为4(第一个3, 1,第一个2;第一个3, 1,第二个2;第二个3, 1,第一个2;第二个3, 1,第二个2,共4个,所以得分为4)。给一个宣传标语,请给出这条标语的得分。

输入

先输入T,表示输入T个测试数据,对于每个测试数据,输入一个字符串,表示一条标语,标语长度<100000。

输出

对于每个测试数据,输出一行,一个数字,表示这条标语的得分(得分不会超过int的表示范围)。

样例输入

1
33122

样例输出

4

来源

[提交][状态]