← 返回题目列表

Codeforces · 1217/C

C. 好子串的数量

中文机器翻译题面 查看原题

给定一个二进制字符串 $$$s$$$ (回想一下,如果每个字符都是 $$$0$$$ 或 $$$1$$$,则该字符串是二进制的)。

令 $$$f(t)$$$ 为以二进制形式写入的整数 $$$t$$$ 的十进制表示形式(可能带有前导零)。例如 $$$f(011) = 3、f(00101) = 5、f(00001) = 1、f(10) = 2、f(000) = 0$$$ 和 $$$f(000100) = 4$$$。

如果 $$$r - l + 1 = f(s_l \dots s_r)$$$,则子字符串 $$$s_{l}, s_{l+1}, \dots , s_{r}$$$ 是好的。

例如字符串 $$$s = 1011$$$ 有 $$$5$$$ 好的子字符串: $$$s_1 \dots s_1 = 1$$$, $$$s_3 \dots s_3 = 1$$$, $$$s_4 \dots s_4 = 1$$$, $$$s_1 \dots s_2 = 10$$$ 和 $$$s_2 \dots s_4 = 011$$$。

你的任务是计算字符串 $$$s$$$ 的好子串的数量。

您必须回答 $$$t$$$ 独立查询。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 查询数量。

每个查询的唯一行包含字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$),仅由数字 $$$0$$$ 和 $$$1$$$ 组成。

保证 $$$\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$$$。

输出

对于每个查询,打印一个整数 — 字符串 $$$s$$$ 的好子串的数量。

示例

输入 #1

4
0110
0101
00001000
0001000

输出 #1

4
3
4
3