CSL的密码2

发布时间: 2018年6月14日 17:53   最后更新: 2018年6月14日 17:57   时间限制: 4000ms   内存限制: 256M

众所周知,CSL最喜欢的密码是******。

为了改变这一点,他随机生成了一个只包含$0$和$1$的字符串,并打算把他的密码改成这个字符串的一个子串

  • 他的密码需要满足以下条件:
  • 密码的二进制表示必须是$3$的倍数,且不能为$0$。

密码中不能含有前导零。

由于他生成的字符串太长了,他希望你帮他数一下他有多少种不同的选择。

两种方案不同当且仅当最后的密码不同。

第一行有一个整数$T$,表示测试数据的组数。
对于每组测试数据,有一个字符串$S$(只包含$0$和$1$)。
$T \leq 100$
$1 \le |S| \le 10^{6}$
$\sum |S| \le 2\cdot 10^{6}$

对于每组测试数据,在一行内输出答案。

复制
4
101010
000111
111000
000000
2
1
4
0

对于第一个样例,两种方案分别为:$10101$,$101010$。

string

ACM集训队暑期集训热身赛