You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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.

## Examples
```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
```
```output
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$$$.

Now solve the problem and return the code.