 Final
 Elimination
 Third qual
 Second qual
 First qual
 Warmup
Second qualification round completed
Tasks
Show one task per page / all tasks on one page
Time limit  2 seconds 

Memory limit  256 megabytes 
Vasya likes to study arrays. Recently his parents presented him with an array a that contains elements equal to 1 and  1. Vasya immediately started to study it.
Additionally Vasya likes zeroes. So he decided to consider various subarrays a[l_{i}, ..., r_{i}] of array a. For each subarray he tries to find the maximum length of its subarray with the sum equal to 0. If there is no such subarray, he considers the answer to be 0. Vasya has written down q subarray requests [l_{i}, r_{i}], and now he wants to find the sum of answers to them.
For example, let us consider sample test.
 subarray [1, 5]: the maximal subarray with sum 0 — [2, 5];
 subarray [1, 3]: the maximal subarray with sum 0 — [2, 3];
 subarray [2, 4]: the maximal subarray with sum 0 — [2, 3];
 subarray [3, 4]: no subarray with sum 0;
 subarray [3, 5]: the maximal subarray with sum 0 — [4, 5].
So the sum of answers for the sample test is 4 + 2 + 2 + 0 + 2 = 10.
Input format 
Input data contains several test cases. The first line contains the number of test cases t (1 ≤ t ≤ 1000). Each of t test cases is described in the following way: the first line of the description contains n — the number of elements of the array (1 ≤ n ≤ 10^{5}). The following line contains n integers a_{i} — elements of the array (a_{i} =  1 or a_{i} = 1). The following line contains q — the number of subarrays that Vasya is interested in (1 ≤ q ≤ 10^{5}). Each of the following q lines contains two integers l_{i}, r_{i} — left and right border of the ith subarray (1 ≤ l_{i} ≤ r_{i} ≤ n) It is guaranteed that the sum of n in all test cases of one input data doesn't exceed 10^{5}, the sum of q in all test cases of one input data doesn't exceed 10^{5}. 

Output format 
For each test output one integer — the sum of answers for the given q subarrays. 
Examples 
Input data
1 5 1 1 1 1 1 5 1 5 1 3 2 4 3 4 3 5
Output data
10 
