C. Количество хороших подстрок
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана бинарная строка $$$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$$$) — количество запросов.

Каждый запрос содержит единственную строку $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), состоящую только из цифр $$$0$$$ и $$$1$$$.

Гарантируется что $$$\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$$$.

Выходные данные

На каждый запрос выведите одно число — количество хороших подстрок строки $$$s$$$.

Пример
Входные данные
4
0110
0101
00001000
0001000
Выходные данные
4
3
4
3