Answer the Queries

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

Let's say, an array $A = \{1001, 3, 5, 5, 99\}$, and $L = 2$, $R = 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 $T$ ($1 ≤ T ≤ 20$), denoting the number of test cases.

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

The next Q lines will contain the queries which is in the form $L$ to $R$ ($0 ≤ 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 $L$ to $R$.

Sample

Input	Output
1 5 3 1001 3 5 5 99 1 2 2 3 0 4	Case 1: 1 2 1