E. Вычислительная машина
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Саши есть две бинарные строки $$$s$$$ и $$$t$$$ одинаковой длины $$$n$$$, состоящие из символов 0 и 1.

Также есть вычислительная машина, которая умеет выполнять два вида операций с бинарными строками $$$a$$$ и $$$b$$$ одинаковой длины $$$k$$$:

  1. Если $$$a_{i} = a_{i + 2} =$$$ 0, то можно присвоить $$$b_{i + 1} :=$$$ 1 ($$$1 \le i \le k - 2$$$).
  2. Если $$$b_{i} = b_{i + 2} =$$$ 1, то можно присвоить $$$a_{i + 1} :=$$$ 1 ($$$1 \le i \le k - 2$$$).

Саше стало интересно следующее: если рассмотреть строку $$$a=s_ls_{l+1}\ldots s_r$$$ и строку $$$b=t_lt_{l+1}\ldots t_r$$$, то какое максимальное количество символов 1 в строке $$$a$$$ можно получить с помощью вычислительной машины. Так как Саша очень любознательный, но ленивый, то вам предстоит ответить на этот вопрос для нескольких интересующих его пар $$$(l_i, r_i)$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина строк $$$s$$$ и $$$t$$$.

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$, состоящую из символов 0 и 1.

Третья строка каждого набора входных данных содержит бинарную строку $$$t$$$ длины $$$n$$$, состоящую из символов 0 и 1.

Четвертая строка каждого набора входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

$$$i$$$-я из следующих строк содержит два целых числа $$$l_{i}$$$ и $$$r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le n$$$) — границы $$$i$$$-й пары подстрок, которые интересуют Сашу.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$q$$$ целых чисел — ответы на все запросы.

Пример
Входные данные
3
4
1111
0000
2
1 2
2 4
4
1010
1101
2
1 3
1 4
6
010101
011010
5
2 3
1 6
2 5
4 4
3 6
Выходные данные
2
3
2
3
1
4
3
1
2
Примечание

В первом наборе входных данных:

  • В первом запросе $$$a =$$$ 11, поэтому максимальное количество символов 1 равно $$$2$$$.
  • Во втором запросе $$$a =$$$ 111, поэтому максимальное количество символов 1 равно $$$3$$$.

Во втором наборе входных данных:

  • В первом запросе $$$a =$$$ 101 и $$$b =$$$ 110. Никаких операций сделать нельзя, поэтому максимальное количество символов 1 равно $$$2$$$.
  • Во втором запросе $$$a =$$$ 1010 и $$$b =$$$ 1101. Так как $$$a_2 = a_4 =$$$ 0, то можно присвоить $$$b_3 :=$$$ 1. Теперь $$$b_1 = b_3 =$$$ 1, поэтому можно присвоить $$$a_2 :=$$$ 1. Строка $$$a$$$ стала равна 1110, поэтому максимальное количество символов 1 равно $$$3$$$.