Tanusera is a famous programmer. Recently he has bought a new car. He loves to play with problems, you know. So, he has decided to make a new problem. He has developed a software & installed it in his car. This software measures the distance passed by the car from time 1 to time N and shows the distance passed by it in every second. You'll be given the data which the software represents. After that Tanusera will ask you Q queries. In each query, he will give you time t1 and time t2. You have to calculate the distance passed by his car from t1 to t2.

Input

Input starts with an integer T, denoting the number of test cases. In each case, there will be two integers N and Q where N denotes the amount of times the software has been performed and Q denotes the number of queries. The next line will contain N integers, i^th integer is the distance passed by the car in ith time. Then there will be Q lines. In each line, there will be two integers t1 and t2.

Constraints

1 <= T <= 3 
1 <= N <= 1000000 
0 <= i^th integer <= 1000000 
1 <= Q <= 1000000 
1 <= t1 <= t2 <= N 

Output

For each case, print the case number and the distance passed by the car from time t1 to time t2 for every query in single line. See the samples for further clarification.

Example

Input:
3
3

5 4
0 0 5 9 2
1 2
1 1
3 5
5 5

3 3
2 0 8
2 3
1 3
2 2

1 1
5
1 1

Output:

Case 1: 
0
0
16
2
Case 2:
8
10
0
Case 3:
5

[ Original setter of this problem is Risal Shahriar Shefin, RUET ]