In a strange city, houses are built in a straight line one after another. There are several communities in the city. Each community consists of some consecutive houses such that every house belongs to exactly one community. The houses are numbered from 1 to n, and the communities are numbered from 1 to c.
Now some inspectors want to find the strongest community considering all houses from i to j. A community is strongest if maximum houses in the range belong to this community. So, there can be more than one strongest community in the range. So, they want to know the number of houses that belong to the strongest community. That's why they are seeking your help.
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing three integers n (1 ≤ n ≤ 105), c (1 ≤ c ≤ n) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers (each between 1 and c) denoting the communities the houses belong to. You can assume that the input follows the restrictions given above, and there are exactly c communities.
Each of the next q lines contains two integers i and j (1 ≤ i ≤ j ≤ n) denoting that the inspectors are asking for the result considering houses from i to j (inclusive).
For each case, print the case number in a single line. Each of the next q lines should contain the number of houses that belong to the strongest community considering houses from i to j. The result should be listed in the same order as they are given in input.
Output for Sample Input
10 3 4
1 1 1 3 3 3 3 2 2 2
3 3 1
3 2 1
Dataset is huge, use faster I/O methods.