CF1978E.Computing Machine

给定长度为 $n$ 的二进制字符串 $s,t$，串内只包含 $0$ 和 $1$，现有 $q$ 次询问，每次给出一个区间 $[l,r]$，分别记 $s,t$ 在 $[l,r]$ 上的子串为 $a,b$，进行任意次如下两种操作：

• 若 $\exist i,i+2\in[l,r]$ 使得 $a_i=a_{i+2}=0$，则可以使 $b_{i+1}$ 的值变为 $1$。
• 若 $\exist i,i+2\in[l,r]$ 使得 $b_i=b_{i+2}=1$，则可以使 $a_{i+1}$ 的值变为 $1$。

现求所有操作结束后，串 $a$ 内最多可以包含多少 $1$。

一个测试点包含多组测试数据，第一行给出 $t(1\leq t \leq 10^4)$，表示测试数据组数。
对于每组数据：
第一行给出一个整数 $n(1\leq n \leq 2\times 10^5)$。
第二、三行给出两个二进制字符串 $s,t$。
第四行给出一个整数 $q$ 表示询问个数。
接下来 $q$ 行，每行两个整数 $l,r$，表示询问区间为 $[l,r]$。

保证 $\sum n$ 和 $\sum q$ 均不超过 $2 \times 10 ^ 5$。

$q$ 行，每行一个整数，表示对应询问的答案。