Distinct Shot Heights

Write a program to calculate the number of distinct shot heights for each query in the given test cases. In each test case, you are given an array of target heights. For each query, which is represented as a pair of indices (L, R), determine the number of distinct heights present in the subarray from position L to R (both inclusive). Note that although the background story mentions that each target's height is reduced by one because of Alex's shot, this operation is applied uniformly to the entire array and therefore does not affect the distinct count.

The input begins with an integer ( T ) (the number of test cases). Each test case starts with two integers ( N ) and ( Q ), where ( N ) is the number of targets and ( Q ) the number of queries. This is followed by ( N ) space-separated integers representing the target heights, and then ( Q ) lines, each containing two integers ( L ) and ( R ) that specify the inclusive range of the query. Your task is to process each query and output the number of distinct target heights in the specified range.

inputFormat

The first line of input contains an integer ( T ), the number of test cases. For each test case:

• The first line contains two integers \( N \) and \( Q \) — the number of targets and the number of queries.
• The second line contains \( N \) space-separated integers representing the target heights.
• Each of the next \( Q \) lines contains two space-separated integers \( L \) and \( R \) indicating the inclusive range for which you need to count the distinct shot heights.

outputFormat

For each query, output a single integer on a new line representing the number of distinct target heights in the range ( [L, R] ).## sample

3
5 3
4 3 5 2 1
1 3
2 5
1 5
4 2
4 3 4 3
1 2
3 4
6 3
1 2 3 4 5 6
1 6
2 5
3 3

3
4
5
2
2
6
4
1