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$。

如果子串 $s_l, s_{l+1}, \dots, s_r$ 满足 $r - l + 1 = f(s_l \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$），表示询问的数量。

每个询问占一行，包含一个仅由数字 $0$ 和 $1$ 组成的字符串 $s$（$1 \le |s| \le 2 \times 10^5$）。

保证所有字符串长度之和 $\sum\limits_{i=1}^{t} |s_i| \le 2 \times 10^5$。

输出格式

对于每个询问，输出一个整数，表示字符串 $s$ 的好子串数量。

输入输出样例 #1

输入 #1

4
0110
0101
00001000
0001000

输出 #1

4
3
4
3