In a strange city, houses are built in a straight line oneafter another. There are several communities in the city. Each communityconsists of some consecutive houses such that every house belongs to exactly one community. The houses are numbered from 1 to n, and thecommunities are numbered from 1 to c.

Now some inspectors want to find the strongest communityconsidering all houses from i to j. A community is strongest ifmaximum houses in the range belong to this community. So, there can be morethan one strongest community in the range. So, they want to know the number ofhouses that belong to the strongest community. That's why they are seeking yourhelp.

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 ≤ 10⁵), c (1 ≤ c ≤ n) and q (1 ≤ q ≤ 50000). The next line contains n space separatedintegers (each between 1 and c) denoting the communities thehouses belong to. You can assume that the input follows the restrictions givenabove, and there are exactly c communities.

Each of the next q lines contains two integers iand j (1 ≤ i ≤ j ≤ n) denoting that the inspectors areasking for the result considering houses from i to j (inclusive).

For each case, print the case number in a single line. Eachof the next q lines should contain the number of houses that belong tothe strongest community considering houses from i to j. Theresult should be listed in the same order as they are given in input.

Dataset is huge, use faster I/O methods.