Given an array of N integers indexed from 1 to N, and q queries, each in the form i j, you have to find the number of distinct integers from index i to j (inclusive).

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 10⁵), q (1 ≤ q ≤ 50000). The next line contains N space separated integers forming the array. There integers range in [0, 10⁵].

Each of the next q lines will contain a query which is in the form i j (1 ≤ i ≤ j ≤ N).

Output

For each test case, print the case number in a single line. Then for each query you have to print a line containing number of distinct integers from index i to j.

Note

Dataset is huge. Use faster I/O methods.

#include<iostream>#include<algorithm>#include<cstdlib>#include<sstream>#include<cstring>#include<bitset>#include<cstdio>#include<string>#include<deque>#include<stack>#include<cmath>#include<queue>#include<set>#include<map>using namespace std;#define INF 0x3f3f3f3f#define CLR(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair<int,int> pii;typedef long long LL;const double PI=acos(-1.0);const int N=100010;const int M=50010;struct info{    int l,r;    int id,b;    bool operator<(const info &t)const    {        if(b==t.b)            return r<t.r;        return b<t.b;    }};info Q[M];int arr[N];int vis[N];int ans[M];int main(void){    int tcase,i,j;    int n,m,l,r;    scanf("%d",&tcase);    for (int q=1; q<=tcase; ++q)    {        scanf("%d%d",&n,&m);        for (i=1; i<=n; ++i)            scanf("%d",&arr[i]);        int unit=(int)sqrt(n);        for (i=1; i<=m; ++i)        {            scanf("%d%d",&Q[i].l,&Q[i].r);            Q[i].id=i;            Q[i].b=Q[i].l/unit;        }        sort(Q+1,Q+1+m);        CLR(vis,0);        int L=1,R=0;        int temp=0;        for (i=1; i<=m; ++i)        {            while (L>Q[i].l)            {                --L;                ++vis[arr[L]];                if(vis[arr[L]]==1)                    ++temp;            }            while (L<Q[i].l)            {                --vis[arr[L]];                if(vis[arr[L]]==0)                    --temp;                ++L;            }            while (R>Q[i].r)            {                --vis[arr[R]];                if(vis[arr[R]]==0)                    --temp;                --R;            }            while (R<Q[i].r)            {                ++R;                ++vis[arr[R]];                if(vis[arr[R]]==1)                    ++temp;            }            ans[Q[i].id]=temp;        }        printf("Case %d:\n",q);        for (i=1; i<=m; ++i)            printf("%d\n",ans[i]);    }    return 0;}