#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (ll)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 1e6 + 10;
const int M = 3e5 + 10;
int A[M], B[M], mx[M], mn[M], pos[M], ans[N];
vector <pair <int, int>> ask[M], add[M];
struct seg{
vector <int> seg;
void ass(int n) {
seg.assign(n * 4 + 100, 0);
}
void upd(int id, int l, int r, int p, int v) {
seg[id] = max(seg[id], v);
if (l == r)
return;
int m = (l + r) / 2;
if (m >= p) {
upd(id * 2, l, m, p, v);
} else {
upd(id * 2 + 1, m + 1, r, p, v);
}
}
int get(int id, int l, int r, int u, int v) {
if (l > v || r < u)
return 0;
if (l >= u && r <= v)
return seg[id];
int m = (l + r) / 2;
return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}
};
int find_mex(int n, int x, int y) {
int l = 0, r = n - 1, ans = -1;
while (l <= r) {
int m = (l + r) / 2;
if (mn[m] >= x && mx[m] <= y) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans + 1;
}
void cal(int n) {
seg seg;
seg.ass(n);
for (int i = 1; i <= n; i++) {
mx[B[i]] = mn[B[i]] = i;
pos[A[i]] = i;
}
for (int i = 1; i < n; i++) {
mx[i] = max(mx[i - 1], mx[i]);
mn[i] = min(mn[i - 1], mn[i]);
}
int l = n, r = 1;
for (int i = 0; i < n; i++) {
l = min(l, pos[i]);
r = max(r, pos[i]);
add[r].pb({l, i + 1 - find_mex(n, l, r)});
}
for (int i = 1; i <= n; i++) {
for (auto x : add[i]) {
seg.upd(1, 1, n, x.f, x.s);
}
for (auto x : ask[i]) {
ans[x.s] = max(seg.get(1, 1, n, x.f, i), ans[x.s]);
}
add[i].clear();
}
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> A[i];
for (int i = 1; i <= n; i++)
cin >> B[i];
int q;
cin >> q;
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
ask[r].pb({l, i});
}
cal(n);
for (int i = 1; i <= n; i++) {
swap(A[i], B[i]);
}
cal(n);
for (int i = 1; i <= n; i++)
ask[i].clear();
for (int i = 1; i <= q; i++) {
cout << ans[i] << "\n";
ans[i] = 0;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
// ab a
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKI2RlZmluZSAgICAgICAgICAgZiAgICAgZmlyc3QKI2RlZmluZSAgICAgICAgICAgcyAgICAgc2Vjb25kCiNkZWZpbmUgICAgICAgICAgIHBiICAgIHB1c2hfYmFjawojZGVmaW5lICAgICAgICAgICBlcCAgICBlbXBsYWNlCiNkZWZpbmUgICAgICAgICAgIGViICAgIGVtcGxhY2VfYmFjawojZGVmaW5lICAgICAgICAgICBsYiAgICBsb3dlcl9ib3VuZAojZGVmaW5lICAgICAgICAgICB1YiAgICB1cHBlcl9ib3VuZAojZGVmaW5lICAgICAgIGFsbCh4KSAgICB4LmJlZ2luKCksIHguZW5kKCkKI2RlZmluZSAgICAgIHJhbGwoeCkgICAgeC5yYmVnaW4oKSwgeC5yZW5kKCkKI2RlZmluZSAgIHVuaXF1ZXYodikgICAgc29ydChhbGwodikpLCAodikucmVzaXplKHVuaXF1ZShhbGwodikpIC0gKHYpLmJlZ2luKCkpCiNkZWZpbmUgICAgIG1lbShmLHgpICAgIG1lbXNldChmICwgeCAsIHNpemVvZihmKSkKI2RlZmluZSAgICAgICAgc3ooeCkgICAgKGxsKSh4KS5zaXplKCkKI2RlZmluZSAgX19sY20oYSwgYikgICAgKDFsbCAqICgoYSkgLyBfX2djZCgoYSksIChiKSkpICogKGIpKQojZGVmaW5lICAgICAgICAgIG14eCAgICAqbWF4X2VsZW1lbnQKI2RlZmluZSAgICAgICAgICBtbm4gICAgKm1pbl9lbGVtZW50CiNkZWZpbmUgICAgY250Yml0KHgpICAgIF9fYnVpbHRpbl9wb3Bjb3VudGxsKHgpCiNkZWZpbmUgICAgICAgbGVuKHgpICAgIChpbnQpKHgubGVuZ3RoKCkpCgpjb25zdCBpbnQgTiA9IDFlNiArIDEwOwpjb25zdCBpbnQgTSA9IDNlNSArIDEwOwoKaW50IEFbTV0sIEJbTV0sIG14W01dLCBtbltNXSwgcG9zW01dLCBhbnNbTl07CnZlY3RvciA8cGFpciA8aW50LCBpbnQ+PiBhc2tbTV0sIGFkZFtNXTsKCnN0cnVjdCBzZWd7CiAgICB2ZWN0b3IgPGludD4gc2VnOwogICAgdm9pZCBhc3MoaW50IG4pIHsKICAgICAgICBzZWcuYXNzaWduKG4gKiA0ICsgMTAwLCAwKTsKICAgIH0KCiAgICB2b2lkIHVwZChpbnQgaWQsIGludCBsLCBpbnQgciwgaW50IHAsIGludCB2KSB7CiAgICAgICAgc2VnW2lkXSA9IG1heChzZWdbaWRdLCB2KTsKICAgICAgICBpZiAobCA9PSByKQogICAgICAgICAgICByZXR1cm47CgogICAgICAgIGludCBtID0gKGwgKyByKSAvIDI7CiAgICAgICAgaWYgKG0gPj0gcCkgewogICAgICAgICAgICB1cGQoaWQgKiAyLCBsLCBtLCBwLCB2KTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICB1cGQoaWQgKiAyICsgMSwgbSArIDEsIHIsIHAsIHYpOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgZ2V0KGludCBpZCwgaW50IGwsIGludCByLCBpbnQgdSwgaW50IHYpIHsKICAgICAgICBpZiAobCA+IHYgfHwgciA8IHUpCiAgICAgICAgICAgIHJldHVybiAwOwoKICAgICAgICBpZiAobCA+PSB1ICYmIHIgPD0gdikKICAgICAgICAgICAgcmV0dXJuIHNlZ1tpZF07CgogICAgICAgIGludCBtID0gKGwgKyByKSAvIDI7CiAgICAgICAgcmV0dXJuIG1heChnZXQoaWQgKiAyLCBsLCBtLCB1LCB2KSwgZ2V0KGlkICogMiArIDEsIG0gKyAxLCByLCB1LCB2KSk7CiAgICB9Cn07CgppbnQgZmluZF9tZXgoaW50IG4sIGludCB4LCBpbnQgeSkgewogICAgaW50IGwgPSAwLCByID0gbiAtIDEsIGFucyA9IC0xOwogICAgd2hpbGUgKGwgPD0gcikgewogICAgICAgIGludCBtID0gKGwgKyByKSAvIDI7CiAgICAgICAgaWYgKG1uW21dID49IHggJiYgbXhbbV0gPD0geSkgewogICAgICAgICAgICBhbnMgPSBtOwogICAgICAgICAgICBsID0gbSArIDE7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgciA9IG0gLSAxOwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gYW5zICsgMTsKfQoKdm9pZCBjYWwoaW50IG4pIHsKICAgIHNlZyBzZWc7CiAgICBzZWcuYXNzKG4pOwogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgbXhbQltpXV0gPSBtbltCW2ldXSA9IGk7CiAgICAgICAgcG9zW0FbaV1dID0gaTsKICAgIH0KCiAgICBmb3IgKGludCBpID0gMTsgaSA8IG47IGkrKykgewogICAgICAgIG14W2ldID0gbWF4KG14W2kgLSAxXSwgbXhbaV0pOwogICAgICAgIG1uW2ldID0gbWluKG1uW2kgLSAxXSwgbW5baV0pOwogICAgfQoKICAgIGludCBsID0gbiwgciA9IDE7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGwgPSBtaW4obCwgcG9zW2ldKTsKICAgICAgICByID0gbWF4KHIsIHBvc1tpXSk7CiAgICAgICAgYWRkW3JdLnBiKHtsLCBpICsgMSAtIGZpbmRfbWV4KG4sIGwsIHIpfSk7CiAgICB9CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgZm9yIChhdXRvIHggOiBhZGRbaV0pIHsKICAgICAgICAgICAgc2VnLnVwZCgxLCAxLCBuLCB4LmYsIHgucyk7CiAgICAgICAgfQoKICAgICAgICBmb3IgKGF1dG8geCA6IGFza1tpXSkgewogICAgICAgICAgICBhbnNbeC5zXSA9IG1heChzZWcuZ2V0KDEsIDEsIG4sIHguZiwgaSksIGFuc1t4LnNdKTsKICAgICAgICB9CgogICAgICAgIGFkZFtpXS5jbGVhcigpOwogICAgfQp9Cgp2b2lkIHNvbHZlKCkgewogICAgaW50IG47CiAgICBjaW4gPj4gbjsKCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICAgICAgY2luID4+IEFbaV07CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQogICAgICAgIGNpbiA+PiBCW2ldOwoKICAgIGludCBxOwogICAgY2luID4+IHE7CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gcTsgaSsrKSB7CiAgICAgICAgaW50IGwsIHI7CiAgICAgICAgY2luID4+IGwgPj4gcjsKICAgICAgICBhc2tbcl0ucGIoe2wsIGl9KTsKICAgIH0KCiAgICBjYWwobik7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICBzd2FwKEFbaV0sIEJbaV0pOwogICAgfQoKICAgIGNhbChuKTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykKICAgICAgICBhc2tbaV0uY2xlYXIoKTsKCiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBxOyBpKyspIHsKICAgICAgICBjb3V0IDw8IGFuc1tpXSA8PCAiXG4iOwogICAgICAgIGFuc1tpXSA9IDA7CiAgICB9Cn0KCmludCBtYWluKCkgewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnRpZSgwKTsKCiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwoKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBzb2x2ZSgpOwogICAgfQoKICAgIHJldHVybiAwOwp9CgovLyBhYiBh