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

static const int MAXN = 100000;

// Structure to hold each query.
struct Query {
    int L, R, K, idx;
};

// Array and frequency count:
int A[MAXN + 1];
int freq[MAXN + 1];      // freq[x] = how many times value x appears in the current subarray
bool used[MAXN + 1];     // used[x] indicates whether x <= currentK (so we count it if freq[x] > 0)
int distinctCount;       // number of distinct values in [1..currentK] that appear in subarray

// Current boundaries for Mo’s
int curL = 0, curR = -1, curK = 0;

// Add element at position pos
void add(int pos) {
    int val = A[pos];
    freq[val]++;
    // If freq becomes 1 and val is within currentK, distinctCount++
    if (freq[val] == 1 && used[val]) {
        distinctCount++;
    }
}

// Remove element at position pos
void remove(int pos) {
    int val = A[pos];
    freq[val]--;
    // If freq becomes 0 and val is within currentK, distinctCount--
    if (freq[val] == 0 && used[val]) {
        distinctCount--;
    }
}

// Move currentK upwards
void incrementK() {
    // curK -> curK+1
    curK++;
    // Mark curK as used
    used[curK] = true;
    // If freq[curK] > 0, it is newly counted as distinct
    if (freq[curK] > 0) {
        distinctCount++;
    }
}

// Move currentK downwards
void decrementK() {
    // If freq[curK] > 0, we will lose that distinct value
    if (freq[curK] > 0) {
        distinctCount--;
    }
    used[curK] = false;
    curK--;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        int N;
        cin >> N;
        for(int i = 0; i < N; i++){
            cin >> A[i];
        }

        int Q;
        cin >> Q;
        vector<Query> queries(Q);
        for(int i = 0; i < Q; i++){
            int l, r;
            cin >> l >> r;
            // Convert to 0-based indexing for consistency.
            l--; 
            r--;
            int k = r - l + 1;
            queries[i] = {l, r, k, i};
        }

        // We choose block sizes for L and R. A common choice is ~ sqrt(N).
        // For K, we also use a block size ~ sqrt(N) to reduce moves in curK.
        int blockSize = (int)cbrt(N > 0 ? N : 1);  // or use sqrt(N). cbrt can also be tried
        if(blockSize < 1) blockSize = 1;          // safety for small N

        // Sort queries by (L/block, R/block, K/block)
        auto getBlockL = [&](int x){ return x / blockSize; };
        auto getBlockK = [&](int x){ return x / blockSize; };

        sort(queries.begin(), queries.end(), [&](const Query &a, const Query &b) {
            int blockA = getBlockL(a.L), blockB = getBlockL(b.L);
            if(blockA != blockB) return blockA < blockB;

            int blockAR = getBlockL(a.R), blockBR = getBlockL(b.R);
            if(blockAR != blockBR) return blockAR < blockBR;

            int blockAK = getBlockK(a.K), blockBK = getBlockK(b.K);
            return blockAK < blockBK;
        });

        // Prepare result array
        vector<int> ans(Q);

        // Initialize data structures for each test case
        curL = 0; 
        curR = -1;
        curK = 0;
        distinctCount = 0;
        memset(freq, 0, sizeof(freq));
        memset(used, false, sizeof(used));

        // Process queries in sorted order
        for(const auto &q : queries) {
            int L = q.L, R = q.R, K = q.K;

            // Move curK to K
            while(curK < K) incrementK();
            while(curK > K) decrementK();

            // Move curR
            while(curR < R) {
                curR++;
                add(curR);
            }
            while(curR > R) {
                remove(curR);
                curR--;
            }

            // Move curL
            while(curL < L) {
                remove(curL);
                curL++;
            }
            while(curL > L) {
                curL--;
                add(curL);
            }

            // Now we have subarray [L..R] and curK = K
            // distinctCount is number of distinct values in [1..K]
            // Minimum changes = subarray length - distinctCount
            int length = R - L + 1;
            ans[q.idx] = length - distinctCount;
        }

        // Print results
        for(int i = 0; i < Q; i++){
            cout << ans[i] << "\n";
        }
    }

    return 0;
}