You are given an array on N elements a[1], a[2], a[3], …. , a[N].

Now you will have to answer some queries.

In every query, you will be given an interval, [l, r]. For this interval you have to print the total summation of happiness of all the elements of the given array between the interval [l, r].

The happiness of an element a[i] between interval [l, r] is: the number of sub-array [lj , rj] where the minimum value between [lj, rj] is equal to a[i]. Here, l <= lj <= i & i <= rj <= r.

Now, you have to print the total summation of happiness of all the elements between [l,r].

Input

The first line of the input contains the number of test cases T. The first line of each test case contains two numbers, N & M. N is the number of elements in array a and M is the number of queries you need to perform.

The next line contains N integers, the array a : a[1], a[2], a[3], … a[N].

Next M lines contains two integers, l & r.

Constraints

1 <= T <= 5

1 <= N, M <= 50000

1 <= a[i] <= 1000000000

1 <= l <= r <= N

Output

For each test case, you need to print the case number on the first line in this format: Case X: where X is the case number.

In the next M lines, you need to print the total summation of happiness of all the elements between [l, r] of the given array.

Example

Input:
2
5 2
1 3 2 4 3
1 3
2 4
5 2
5 3 7 6 8
1 4
2 5 

Output:
Case 1:
6
6
Case 2:
10
10

Problem Setter: Raihat Zaman Neloy. 
Used in Eid 2016 contest. 
More about Eid 2016 contest: Click Here