Computing Machine
Contest: Codeforces Round 953 (Div. 2)
Difficulty rating: 2000
Tags: brute force, data structures, dp, greedy, implementation

Sasha has two binary strings $$$s$$$ and $$$t$$$ of the same length $$$n$$$, consisting of the characters 0 and 1.

There is also a computing machine that can perform two types of operations on binary strings $$$a$$$ and $$$b$$$ of the same length $$$k$$$:

1. If $$$a_{i} = a_{i + 2} =$$$ 0, then you can assign $$$b_{i + 1} :=$$$ 1 ($$$1 \le i \le k - 2$$$).
2. If $$$b_{i} = b_{i + 2} =$$$ 1, then you can assign $$$a_{i + 1} :=$$$ 1 ($$$1 \le i \le k - 2$$$).

Sasha became interested in the following: if we consider the string $$$a=s_ls_{l+1}\ldots s_r$$$ and the string $$$b=t_lt_{l+1}\ldots t_r$$$, what is the maximum number of 1 characters in the string $$$a$$$ that can be obtained using the computing machine. Since Sasha is very curious but lazy, it is up to you to answer this question for several pairs $$$(l_i, r_i)$$$ that interest him.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the strings $$$s$$$ and $$$t$$$.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$, consisting of the characters 0 and 1.

The third line of each test case contains a binary string $$$t$$$ of length $$$n$$$, consisting of the characters 0 and 1.

The fourth line of each test case contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

The $$$i$$$-th of the following lines contains two integers $$$l_{i}$$$ and $$$r_{i}$$$ ($$$1 \le l_{i} \le r_{i} \le n$$$) — the boundaries of the $$$i$$$-th pair of substrings that interest Sasha.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$q$$$ integers — the answers to all queries.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

- In the first query, $$$a =$$$ 11, so the maximum number of 1 characters is $$$2$$$.
- In the second query, $$$a =$$$ 111, so the maximum number of 1 characters is $$$3$$$.

In the second test case:

- In the first query, $$$a =$$$ 101 and $$$b =$$$ 110. No operations can be performed, so the maximum number of 1 characters is $$$2$$$.
- In the second query, $$$a =$$$ 1010 and $$$b =$$$ 1101. Since $$$a_2 = a_4 =$$$ 0, we can assign $$$b_3 :=$$$ 1. Now $$$b_1 = b_3 =$$$ 1, so we can assign $$$a_2 :=$$$ 1. The string $$$a$$$ becomes 1110, so the maximum number of 1 characters is $$$3$$$.

Example input:
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

Example output:
2
3
2
3
1
4
3
1
2

Editorial:
Notice that it is advantageous to perform only operations of the first type first, and then only operations of the second type. Perform all possible operations of the first type on the string $$$t$$$ and save it in $$$t'$$$. Perform all possible operations of the second type on the string $$$s$$$, using $$$t'$$$, and save it in $$$s'$$$. Calculate the prefix sums on the string $$$s'$$$. Let $$$len$$$ be the length of the query range. The answer to queries with small length ranges ($$$len < 5$$$) can be computed by simulating the proposed process. For longer strings, it can be guaranteed that in the string $$$a$$$ with the maximum number of 1 characters, $$$a_{3}a_{4}\ldots a_{len - 2}$$$ will match the characters $$$s'_{3}s'_{4}\ldots s'_{len - 2}$$$, their count can be found using prefix sums. Separately check if $$$a_{1}$$$, $$$a_{2}$$$, $$$a_{len - 1}$$$, $$$a_{len}$$$ can become 1.