You are given an array of N integers.
You have to answer Q queries.
Each query contains two integers L and R
For each query print the sum of integers in array from index L to R

Input :

First line will contain an integer T (number of test cases).
T blocks of line follows.
First line of each block contains an integer N (number of array elements).
Next line contains N integers (array elements).
Next line contains an integer Q (number of queries).
Next Q lines contain two integers L and R

Ouput :

Print required answer for each query

Constraints:

1<=T<=10
1<=N<=10^5
0<=a[i]<=10^9
1<=Q<=10^5
1<=L<=R<=N