Given n integers and q queries, in which each query defines a range, find the sum of the n given integers within this range.
The first line contains an integer t, which indicates the number of test cases. In each test case, the first line contains an integer n (n<=100000), specifying how many integers will be given. The next line contains n integers, in which the ith integer represents ai (-50000 <= ai <= 50000). The followed line contains a positive integer q (q <= 10000), 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.