Description

Given a sequence A = a₁, a₂, ..., a_N.

A continuous subsequence A[L ... R] = a_L, ..., a_R of  A is called very beautiful if every element in A[L...R] is unique.

There will be Q queries.

In the i-th query, you'll be given L_i and R_i and you have to find the minimum number of elements needed to be removed to make the subsequence A[L_i...R_i] very beautiful.

It is guaranteed for each i = 1, 2, ..., Q - 1, L_i ≤ L_i+1 and R_i ≤ R_i+1.

 

For example, if A = [1, 3, 3, 4, 1] and L = 1, R = 5.

You can remove A[1] and A[3] to make A very beautiful.

On the other hand, removing one element is not enough to make A very beautiful.

Hence, the minimum number of elements needed to be removed is 2 in this example.

 

It is recommended to include<stdio.h> and use scanf/printf instead of cin/cout to speed up input and output.

You may need to select c++11, c++14, c++17 as the compiler to avoid compile error.

 

Input

The first line of the input contains an integer T, the number of testcases.

The first line of each testcase contains two integers N Q, the length of A and the number of queries.

The second line of each testcase contains N integers, a₁, a₂, ..., a_N.

Each of the next Q lines contains two integers L_i R_i, the subsequence you are queied.

 

For each test,

1. N ≤ 100, Q ≤ 100
2. N ≤ 100, Q ≤ 100
3. N ≤ 1000, Q ≤ 1000
4. N ≤ 1000, Q ≤ 1000
5. N ≤ 200000, Q ≤ 100000
6. N ≤ 200000, Q ≤ 100000

T ≤ 10, 1 ≤ a_i ≤ 10⁹, 1 ≤ L_i ≤ R_i ≤ N.

 

Output

For each query in each testcase, please print the minimum number of element needed to be removed to make the subsequence very beautiful.

You have to print an extra new line at the end of each testcase, including the last one.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss