Server Time: Sun Sep 24, 2017 1:56 pm
Welcome ( logout
1339 - Strongest Community
  PDF (English) Statistics Forum
Time Limit: 3 second(s) Memory Limit: 64 MB

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

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).

Output

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.

Sample Input

Output for Sample Input

2

10 3 4

1 1 1 3 3 3 3 2 2 2

1 5

1 6

1 7

7 9

3 3 1

3 2 1

1 1

Case 1:

3

3

4

2

Case 2:

1

Note

Dataset is huge, use faster I/O methods.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan