B'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 : 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. Each test consists of multiple test cases. The first line contains a single integer t ( 1 <= t <= 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 <= n <= 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 <= q <= 2 cdot 10^5 ) -- the number of queries. The i -th of the following lines contains two integers l_{i} and r_{i} ( 1 <= l_{i} <= r_{i} <= 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 . For each test case, output q integers -- the answers to all queries. In the first test case: In the second test case: '...