Computing Machine
Description
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$:
- If $a_{i} = a_{i + 2} =$ 0, then you can assign $b_{i + 1} :=$ 1 ($1 \le i \le k - 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.
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$.
For each test case, output $q$ integers — the answers to all queries.
Input
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
For each test case, output $q$ integers — the answers to all queries.
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
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$.