#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int arr[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[arr[idx]]++;
    if(cnt[arr[idx]]==1)
        distinct_elements++;
}
void del(int idx)
{
    cnt[arr[idx]]--;
    if(cnt[arr[idx]]==0)
        distinct_elements--;
}
int main()
{
    //freopen("t.txt","w",stdout);
    int t,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        memset(ans,0,sizeof(ans));
        scanf("%d %d",&n,&q);
        for(int i=0; i<n; i++)
        {
            scanf("%d", &arr[i]);
        }
        block_size = sqrt(n);
        for(int i=0; i<q; i++)
        {
            scanf("%d %d",&query[i].L,&query[i].R);
            --query[i].L;
            --query[i].R;
            query[i].index=i;
        }
        sort(query, query+q);
        int curL = 0, curR =-1;
        distinct_elements = 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]);
        }
    }
}