#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(s) (int)(s).size()
#define all(s) s.begin(),s.end()

void Speed() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

struct Node {
    vector<int> r, mex;
} neutral;

struct segtree {
    segtree *left = nullptr, *right = nullptr;

    Node node = {};

    int start, end;

    segtree(int l = 0, int r = 0) : start(l), end(r) {}

    void extend() {
        if (left == nullptr) {
            int mid = start + end >> 1;
            left = new segtree(start, mid);
            right = new segtree(mid + 1, end);
        }
    }

    Node pushup(Node a, Node b) {
        Node ret;
        int i = 0, j = 0, last = 0;
        while(i < sz(a.r) || j < sz(b.r)){
            if(j == sz(b.r) || (i < sz(a.r) && a.r[i] < b.r[j])){
                ret.r.push_back(a.r[i]);
                last = max(last, a.mex[i++]);
                ret.mex.push_back(last);
            }
            else{
                ret.r.push_back(b.r[j]);
                last = max(last, b.mex[j++]);
                ret.mex.push_back(last);
            }
        }
        return ret;
    }

    void build(vector<vector<array<int, 2>>>& v) {
        if (start == end) {
            for(auto& [r, mex] : v[start]){
                node.r.push_back(r), node.mex.push_back(mex);
            }
            return;
        }
        extend();
        left->build(v);
        right->build(v);
        node = pushup(left->node, right->node);
    }

    int query(int l, int r) {
        if (r < start || end < l)
            return 0;
        extend();
        if (l <= start && end <= r){
            int idx = upper_bound(all(node.r), r) - node.r.begin();
            if(idx == 0) return 0;
            return node.mex[--idx];
        }
        return max(left->query(l , r), right->query(l , r));
    }

    ~segtree() {
        if (left == nullptr)return;
        delete left;
        delete right;
    }
};

void solve() {
    int n; cin >> n;
    array<vector<int>, 2> a;
    a[0] = a[1] = vector<int>(n);
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }

    vector<vector<array<int, 2>>> v(n);
    auto doWork = [&](){
        vector<int> idx(n), freq1(n + 1), freq2(n + 1);
        for(int i = 0; i < n; i++) idx[a[0][i]] = i;
        int l = idx[0], r = idx[0];
        freq1[0] = 1; freq2[a[1][l]] = 1;
        int mex1 = 0, mex2 = 0;
        while(freq1[mex1]) mex1++;
        while(freq2[mex2]) mex2++;
        v[l].push_back({r, abs(mex1 - mex2)});
        for(int k = 1; k < n; k++){
            int new_l = min(l, idx[k]), new_r = max(r, idx[k]);
            for(int j = new_l; j < l; j++){
                freq1[a[0][j]] = 1;
                freq2[a[1][j]] = 1;
            }
            for(int j = r + 1; j <= new_r; j++){
                freq1[a[0][j]] = 1;
                freq2[a[1][j]] = 1;
            }
            l = new_l; r = new_r;
            while(freq1[mex1]) mex1++;
            while(freq2[mex2]) mex2++;
            v[l].push_back({r, abs(mex1 - mex2)});
        }
    };
    doWork();
    swap(a[0], a[1]);
    doWork();
    for(int l = 0; l < n; l++) sort(all(v[l]));

    vector<tuple<int, int, int>> st;
    for(int l = 0; l < n; l++){
        int last_r = -1, last_mex = -1;
        for(auto& [r, mex] : v[l]){
            if(r == last_r && mex == last_mex) continue;
            last_r = r; last_mex = mex;
            st.push_back({l, r, mex});
        }
    }

    // segtree* root = new segtree(0, n - 1);
    // root->build(v);
    int q; cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        l--; r--;
        int ans = 0;
        for(auto& [a, b, mex] : st){
            if(a > r) break;
            if(a >= l && b <= r) ans = max(ans, mex);
        }
        cout << ans << '\n';
    }
}

int main() {
    Speed();
    int tc = 1;
    cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}