Kimi has a lot of candies, and divides them into piles, where theith pile containsAicandies. Each time Kimi will choose an interval[l,r], and calculate the total amount ofAl,Al+1,…,Ar. It's a hard task, and you're required to solve it.

An integerT(T≤10)will exist in the first line of input, indicating the number of test cases. Each test case begins with the number of pilesN(1≤N≤10⁵). The second line containsNintegersAi(1≤Ai≤100), whereAistands for the number of candies in theith pile. The next line is the number of queriesM(1≤M≤10⁵). The nextMlines, each with two integersl,r(1≤l≤r≤N), describe the queried intervals.

For each test case, output the total amount of candies in the queried interval.