Given n integers and q queries, in which each query defines a range, find the sum of the n given integers within the range.
The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases. In each test case, the first line contains an integer n (n <= 105), specifying how many integers will be given. The next line contains n integers, in which the ith integer represents ai (-231 <= ai <= 231-1). The followed line contains a positive integer q (q <= 105), denoting the number of queries. Next q lines define q queries, one per line. Each query is specified by two integers a and b (1 <= a <= b <= n), meaning a range, in which the partial sum of the given integers are queried.
For each query, output a line with the partial sum of the given integers within the queried range.