Given an array of ‘N’ integers and ‘Q’ queries. The query is defined as below :-

Given 2 integers ‘l’ and ‘r’ (‘l’ >= 0 and ‘r’ < N) find the maximum subarray sum between ‘l’ to ‘r’ (Inclusive).

Query( ‘l’ ,’r’) = max(arr[i] + arr[i+1] +...arr[j].( i >= ‘l’ and j <= ‘r’)

Input Format :

The first line contains ‘T,’ denoting the number of test cases.

The first line of the test case contains a single integer ‘N’  denoting the size of the ‘arr’ array.

The second line of each test case contains ‘N’ space-separated integers denoting the array ‘arr’.

The third line of each test case contains an integer ‘Q’ denoting the number of queries.

The next ‘Q'  lines of each test case contain 2 space-separated integers denoting the following:

The first integer denotes ‘l’ and the second integer denotes ‘r’  which are the range for which we need to calculate max(arr[i] + arr[i+1] +...arr[j].( i >= ‘l’ and j <= ‘r’).

Output Format :

For each query print an integer denoting the maximum possible value.in the range of ‘l’ and ‘r’.

The output for each test case will be printed in a separate line.

Note :

You need not to print anything. It has been already taken care of. Just implement the function.

Constraints :

 1 <= T <= 5
 1 <= N <= 10^5
 1 <= Q <= 10^5
 -10^9 <= arr[i] <= 10^9

Where ‘arr[i]’ is the value of the element at index ‘i’.

Time Limit: 1 sec