#include<bits/stdc++.h>
#define pir pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=15010;
int T;
int n,q;
int a[N];
int nxt[N],pos[N];
pair<int,int> to[N][20]; //跳一次能到哪；中间有几个空缺
void clear()
{
    return;
}
void work()
{
    clear();
    n=re();
    for(int i=1;i<=n;i++) a[i]=re();
    for(int i=1;i<=13;i++) pos[i]=n+1;
    for(int i=n;i>=1;i--)
    {
        nxt[i]=pos[a[i]];
        pos[a[i]]=i;
    }
    // for(int i=1;i<=n;i++) cout<<nxt[i]<<' ';cout<<endl;
    for(int i=1;i<=n;i++)
    {
        int idx=n+1;
        for(int j=i;j<=n;j++)
        {
            if(nxt[j]<=n)
            {
                idx=j;
                break;
            }
        }
        if(idx==n+1) to[i][0]=mp(n+1,n-i+1);
        else to[i][0]=mp(nxt[idx],idx-i);
    }
    // for(int i=1;i<=n;i++) cout<<i<<' '<<to[i][0].fi<<' '<<to[i][0].se<<endl;
    for(int j=1;j<=18;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(to[i][j-1].fi+1>=n+1||to[to[i][j-1].fi+1][j-1].fi==n+1) to[i][j]=mp(n+1,n-i+1);
            else to[i][j]=mp(to[to[i][j-1].fi+1][j-1].fi,to[i][j-1].se+to[to[i][j-1].fi+1][j-1].se);
        }
    }
    // cout<<"********"<<to[2][1].fi<<' '<<to[2][1].se<<endl;
    q=re();
    for(int i=1,l,r;i<=q;i++)
    {
        l=re();r=re();
        int ans=0,now=l;
        for(int k=18;k>=0;k--)
        {
        // cout<<"***"<<k<<' '<<ans<<' '<<now<<endl;
            if(to[now][k].fi<=r) ans+=to[now][k].se,now=to[now][k].fi+1;
            if(now>r) break;
        }
        // cout<<"***"<<ans<<' '<<now<<endl;
        if(now<=r)
        {
            ans+=r-now+1;
            for(int j=now;j<=r;j++)
            {
                if(nxt[j]<=r) ans-=nxt[j]-j+1,j=nxt[j];
            }
        }
        printf("%d\n",ans);
    }
    return;
}
int main()
{
    freopen("bamboo.in","r",stdin);
    freopen("bamboo.out","w",stdout);
    T=re();
    while(T--) work();
    return 0;
}