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.

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.

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$$$.

Idx	Name	Rating
A	Alice and Books	800
B	New Bakery	800
C	Manhattan Permutations	1300
D	Elections	1600
E	Computing Machine	2000
F	Large Graph	2400

Codeforces Round 953 (Div. 2)