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

const int N = 15005;
const int LOG = 15;

int a[N], b[N], c[N][LOG + 1];
int nxt[14];

int T, n, q;

int gps(int i, int len, const int& N) {
    len = min(len, N - i);
    if (len <= 0) return -1;
    int j = 0;
    while ((1 << (j + 1)) < len) j++;
    if ((1 << j) == len && c[i][j] != -2) return c[i][j];
    int left_len = 1 << j;
    int x = c[i][j];
    if (x == -1) return gps(i + left_len, len - left_len, N);
    if (b[x] >= i + len) return x;
    int new_i = b[x] + 1;
    int new_len = len - (new_i - i);
    return gps(new_i, new_len, N);
}

int calc(int i, int len, const int& N) {
    len = min(len, N - i);
    if (len <= 0) return 0;
    int x = gps(i, len, N);
    if (x == -1) return 0;
    return 1 + calc(x + 1, len - (x + 1 - i), N);
}

int main() {
    freopen("bamboo.in","r",stdin);
    freopen("bamboo.out","w",stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        for (int v = 1; v <= 13; v++) nxt[v] = n;
        for (int i = n - 1; i >= 0; i--) {
            int v = a[i];
            b[i] = nxt[v];
            nxt[v] = i;
        }
        for (int i = 0; i < n; i++) {
            c[i][0] = i;
            for (int j = 1; j <= LOG; j++) {
                c[i][j] = -2;
            }
        }
        for (int j = 1; j <= LOG; j++) {
            for (int i = 0; i < n; i++) {
                int len = 1 << j;
                if (i + len > n) continue;
                c[i][j] = gps(i, len, n);
            }
        }
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
        	int l,r,len;
        	scanf("%d%d",&l,&r);
        	l--;
        	r--;
        	len=r-l+1; 
            printf("%d\n",calc(l,len,n));
        }
    }
    return 0;
}