给定一个二进制字符串 $$$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