Answer the Queries

Limits 1s, 512 MB

Given an array of NN elements, indexed from 0 to N1N-1. Now you are given some queries in the form [L,R][L, R] inclusive. Your task is to find the number of occurrence of the highest value from LL to RR.

Let's say, an array A={1001,3,5,5,99}A = \{1001, 3, 5, 5, 99\}, and L=2L = 2, R=3R = 3. So, here the highest value from index 2 to 3 is 5 and the number of occurrence of 5 is exactly 2. So, you have to print 2.

Input

Input begins with an integer TT (1T201 ≤ T ≤ 20), denoting the number of test cases.

Each case starts with two integers NN and QQ (1N,Q1041 ≤ N, Q ≤ 10^4). The next line contains N space separated integers forming the array AA (2×105<A[i]<2x105-2 \times 10^5 < A[i] < 2x10^5).

The next Q lines will contain the queries which is in the form LL to RR (0LR<N0 ≤ L ≤ R < N).

Output

For each test case, print the case number in a single line. Then for each query you have to print the number of occurrence of the maximum number between index LL to RR.

Sample

InputOutput
1
5 3
1001 3 5 5 99
1 2
2 3
0 4
Case 1:
1
2
1