#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000005;

int ara[maxn], ans[maxn], cnt[maxn], n, q, block_size;

struct Query {
    int index, L, R;
    bool operator<(const Query& other) {
        return L/block_size < other.L/block_size ||
               (L/block_size == other.L/block_size && R<other.R);
    }

} query[maxn];

int distinct_elements;

void add(int idx) {
    cnt[ara[idx]]++;
    if(cnt[ara[idx]]==1)
        distinct_elements++;
}
void del(int idx) {
    cnt[ara[idx]]--;
    if(cnt[ara[idx]]==0)
        distinct_elements--;
}
int main()
{
    int t,cas=0;
    scanf("%d",&t);

    while(t--)
    {
        memset(ans,0,sizeof(ans));
        memset(cnt,0,sizeof(cnt));
        scanf("%d %d", &n,&q);
        for(int i=1; i<=n; i++)
        {
            scanf("%d", &arr[i]);
        }
        block = sqrt(n);
        for(int i=0; i<q; i++)
        {
            scanf("%d %d", &query[i].L, &query[i].R);
            query[i].index = i;
        }
        sort(query, query+q);
        int curL = 0, curR = -1;
        dis = 0;
        for(int i=0; i<q; i++)
        {
            int query_index = query[i].index;
            int l = query[i].L;
            int r = query[i].R;

            while(curL<l)
                del(curL++);
            while(curL>l)
                add(--curL);
            while(curR<r)
                add(++curR);
            while(curR>r)
                del(curR--);
            ans[query_index] = distinct_elements;
        }
        printf("Case %d:\n",cas++);
        for(int i=0; i<q; i++)
        {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}