Kimi has a lot of candies, and divides them into piles, where the ith pile contains Ai candies. Each time Kimi will choose an interval [l,r], and calculate the total amount of Al,Al+1,…,Ar. It's a hard task, and you're required to solve it.
An integer T(T≤10) will exist in the first line of input, indicating the number of test cases. Each test case begins with the number of piles N(1≤N≤105). The second line contains N integers Ai(1≤Ai≤100), where Ai stands for the number of candies in the ith pile. The next line is the number of queries M(1≤M≤105). The next M lines, each with two integers l,r(1≤l≤r≤N), describe the queried intervals.
For each test case, output the total amount of candies in the queried interval.
1
5
1 2 4 5 9
3
1 2
2 4
4 5
3
11
14