#include<iostream>

using namespace std;

const int N = 1e4 + 5e3 + 10, M = 13, inf = 1e9;
int t, n, q, wl, wr, a[N], r[N], rn[M], nxt[N][M], cnt = 0;

int read_int(){
    int x = 0; char ch = ' '; while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();} return x;
}

int main(){
	t = read_int();
	while(t--){
		for(int i = 0; i < M; i++) rn[i] = inf;
		n = read_int();
		for(int i = 1; i <= n; i++){
			a[i] = read_int();
			if(rn[a[i]] != inf){
				r[rn[a[i]]] = i;
			}
			r[i] = inf; rn[a[i]] = i;
		}
		for(int i = 1; i <= n; i++) nxt[i][0] = r[i];
		for(int i = 1; i < M; i++){
			for(int j = 1; j <= n; j++){
				if(nxt[j][i-1]+1 > n) nxt[j][i] = inf;
				else nxt[j][i] = nxt[nxt[j][i-1]+1][i-1];
			}
		}
		q = read_int();
		while(q--){
			wl = read_int(); wr = read_int();
			cnt = 0;
			for(int i = wl; i <= wr;){
				if(r[i] > wr){
					cnt++; i++;
					continue;
				}
				for(int j = M-1; j >= 0; j--){
					if(nxt[i][j] <= wr) i = nxt[i][j] + 1;
				}
			}
			cout << cnt << '\n';
		}
	}
	return 0;
}