Кошма Туэ — Морса
Войлочную кошму из Нарына выкладывают из полосок двух цветов: светлых (0) и тёмных (1). Мастер раскладывает полоски по последовательности Туэ — Морса:
t[0] = 0;t[2i] = t[i],t[2i + 1] = 1 − t[i].
Получается 0110100110010110…: каждый следующий блок длины 2^k — это предыдущий блок с заменой цветов. Эта последовательность нигде не содержит трёх одинаковых блоков подряд, поэтому узор не надоедает глазу.
Покупатель хочет найти на кошме любимый рисунок — строку s из нулей и единиц. Сколько раз s встречается (вхождения могут перекрываться) среди первых N полосок t[0], t[1], …, t[N − 1]?
Входные данные
В первой строке — число q (1 ≤ q ≤ 500). В каждой из следующих q строк — целое число N и строка s через пробел (1 ≤ N ≤ 10¹⁸, 1 ≤ |s| ≤ 40, s состоит из символов 0 и 1).
Выходные данные
Для каждого запроса выведите количество позиций i (0 ≤ i ≤ N − |s|), для которых t[i] t[i+1] … t[i+|s|−1] = s.
Пример 1
Вход:
4
16 11
16 000
16 0110
1000 1
Выход:
3
0
3
500
Пояснение
Первые 16 полосок: 0110100110010110. Строка 11 встречается в них 3 раза (с позиций 1, 5 и 11). Строки 000 в последовательности нет вообще.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов N ≤ 2 · 10⁵.
Комментарии