Вам задана бинарная строка \(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\) независимых запросов.