#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mx = 1e5+10;
ll arr[mx],tree[mx*4],ans[50010];
vector<ll>V;
vector<pair<ll,pair<ll,ll> >>pa;
void update(ll node,ll b,ll e,ll i,ll val)
{
    if(b==e)
    {
        tree[node] = val;
        return;
    }
    ll mid = (b+e)/2;
    ll left = node*2;
    ll right = node*2+1;
    if(b<=i && i<=mid)
    {
        update(left,b,mid,i,val);
    }
    else
    {
        update(right,mid+1,e,i,val);
    }
    tree[node] =tree[left]+tree[right];
}
ll query(ll node,ll b,ll e,ll i,ll j)
{
    if(i<=b && j>=e)
    {
        return tree[node];
    }
    if(j<b || i >e)
        return 0;
    ll mid =(b+e)/2;
    ll left = node*2;
    ll right = node*2+1;
    ll p = query(left,b,mid,i,j);
    ll q = query(right,mid+1,e,i,j);
    return (p+q);
}
void clr()
{
    V.clear();
    memset(tree,0,sizeof(tree));
    memset(arr,-1,sizeof(arr));
    pa.clear();
}
int main()
{
    ll t,cas=1;
    scanf("%lld",&t);
    while(t--)
    {
        ll n,q,r,l,c;
        ll a,b;
        scanf("%lld %lld",&n,&q);
        clr();
        V.push_back(0);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a);
            V.push_back(a);
        }
        for(int i=1; i<=q; i++)
        {
            scanf("%lld %lld",&a,&b);
            pa.push_back(make_pair(b,make_pair(a,i)));
        }
        sort(pa.begin(),pa.end());
        int j=0;
        for(int i=0; i<q; i++)
        {
            r = pa[i].first;
            l = pa[i].second.first;
            c = pa[i].second.second;
            while(j<r)
            {
                j++;
                a = V[j];
                if(arr[a]==-1)
                {
                    update(1,1,n,j,1);
                    arr[a]=j;
                }
                else
                {
                    update(1,1,n,arr[a],0);
                    update(1,1,n,j,1);
                    arr[a]=j;
                }
            }
            ll x = query(1,1,n,l,r);
            ans[c]=x;
        }
        printf("Case %lld:\n",cas++);
        for(int i=1; i<=q; i++)
            printf("%lld\n",ans[i]);
    }
}