1978E - Computing Machine - CodeForces Solution

for _ in range(int(input())):
    n = int(input())
    a = input()
    b = input()

    b_modified = list(b)
    for i in range(n - 2):
        if a[i] == a[i + 2] == '0':
            b_modified[i + 1] = '1'
    a_modified = list(a)
    for i in range(n - 2):
        if b_modified[i] == b_modified[i + 2] == '1':
            a_modified[i + 1] = '1'
    
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + int(a_modified[i - 1])
    
    for _ in range(int(input())):
        l, r = map(int, input().split())

        res = prefix_sum[r] - prefix_sum[l - 1]

        res -= a_modified[l - 1] == '1' and a[l - 1] == '0'
        if l < r:
            res -= a_modified[r - 1] == '1' and a[r - 1] == '0'

        if l + 1 < r:
            res -= a_modified[l] == '1' and a[l] == '0' and (b[l - 1] == '0' or (l + 2 == r and b[r - 1] == '0'))
        if l + 2 < r:
            res -= a_modified[r - 2] == '1' and a[r - 2] == '0' and b[r - 1] == '0'

        print(res)