Sasha有两个二进制字符串$$$s$$$和$$$t$$$,长度相同$$$n$$$,由字符0和1组成。
还有一种计算机可以对相同长度$$$k$$$的二进制串$$$a$$$和$$$b$$$进行两种操作:
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$$$)。
Sasha 对以下问题感兴趣:如果我们考虑字符串 $$$a=s_ls_{l+1}\ldots s_r$$$ 和字符串 $$$b=t_lt_{l+1}\ldots t_r$$$,那么使用计算机可以获取字符串 $$$a$$$ 中 1 个字符的最大数量是多少。由于 Sasha 很好奇但很懒,因此由您来回答他感兴趣的几对 $$$(l_i, r_i)$$$ 的问题。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$s$$$ 和 $$$t$$$ 的长度。
每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$,由字符0和1组成。
每个测试用例的第三行包含一个长度为$$$n$$$的二进制字符串$$$t$$$,由字符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$$$) — Sasha 感兴趣的第 $$$i$$$ 对子字符串的边界。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$q$$$ 整数 - 所有查询的答案。
示例
输入 #1
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
输出 #1
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$$$。