#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int n, m;
    std::cin >> n >> m;
    std::cout << std::max(n, m) + 1 << "\n";
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    std::vector<int> cnt = {1};
    for (int i = 1; i < n; i++) {
        if (a[i] == a[i - 1]) {
            cnt.back()++;
        } else {
            cnt.emplace_back(1);
        }
    }
    std::sort(cnt.begin(), cnt.end());
    int m = cnt.size();
    for (int i = 0; i < m - 1; i++) {
        if (cnt[i] > k) {
            std::cout << m - i << "\n";
            return;
        }
        k -= cnt[i];
    }
    std::cout << 1 << "\n";
}

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

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int l, r;
    std::cin >> l >> r;
    int k = 31 - __builtin_clz(l ^ r);
    int a = l | ((1 << k) - 1), b = a + 1, c = (a == l ? r : l);
    std::cout << a << " " << b << " " << c << "\n";
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using i64 = long long;

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;

    SegmentTree() : n(0) {}

    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }

    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }

    void init(int n_, Info v_ = Info()) {
        init(std::vector<Info>(n_, v_));
    }

    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        int sz = (1 << (std::__lg(n - 1) + 1));
        info.assign(sz * 2, Info());
        std::function<void(int, int, int)> build = [&](int v, int l, int r) {
            if (l == r) {
                info[v] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(v + v, l, m);
            build(v + v + 1, m + 1, r);
            info[v] = info[v + v] + info[v + v + 1];
        };
        build(1, 0, n - 1);
    }

    Info rangeQuery(int v, int l, int r, int tl, int tr) {
        if (r < tl || l > tr) {
            return Info();
        }
        if (l >= tl && r <= tr) {
            return info[v];
        }
        int m = (l + r) / 2;
        return rangeQuery(v + v, l, m, tl, tr) + rangeQuery(v + v + 1, m + 1, r, tl, tr);
    }

    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n - 1, l, r);
    }

    void modify(int v, int l, int r, int i, const Info &x) {
        if (l == r) {
            info[v] = x;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) {
            modify(v + v, l, m, i, x);
        } else {
            modify(v + v + 1, m + 1, r, i, x);
        }
        info[v] = info[v + v] + info[v + v + 1];
    }

    void modify(int i, const Info &x) {
        modify(1, 0, n - 1, i, x);
    }

    Info query(int v, int l, int r, int i) {
        if (l == r) {
            return info[v];
        }
        int m = (l + r) / 2;
        if (i <= m) {
            return query(v + v, l, m, i);
        } else {
            return query(v + v + 1, m + 1, r, i);
        }
    }

    Info query(int i) {
        return query(1, 0, n - 1, i);
    }
};

const int INF = 1E9;

struct Info {
    int min1, min2, max1, max2, ans1, ans2;

    Info() : min1(INF), min2(INF), max1(-INF), max2(-INF), ans1(0), ans2(0) {}

    Info(std::pair<int, int> x) : min1(x.first), min2(x.second), max1(x.first), max2(x.second), ans1(0), ans2(0) {}
};

Info operator+(const Info &a, const Info &b) {
    Info res;
    res.min1 = std::min(a.min1, b.min1);
    res.min2 = std::min(a.min2, b.min2);
    res.max1 = std::max(a.max1, b.max1);
    res.max2 = std::max(a.max2, b.max2);
    res.ans1 = std::max({a.ans1, b.ans1, b.max1 - a.min1});
    res.ans2 = std::max({a.ans2, b.ans2, a.max2 - b.min2});
    return res;
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    std::vector<std::pair<int, int>> t(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        t[i] = {a[i] - i, a[i] + i - n + 1};
    }
    SegmentTree<Info> st(t);
    auto query = [&]() {
        return std::max(st.info[1].ans1, st.info[1].ans2);
    };
    std::cout << query() << "\n";
    for (int i = 0; i < q; i++) {
        int p, x;
        std::cin >> p >> x;
        p--;
        t[p] = {x - p, x + p - n + 1};
        st.modify(p, t[p]);
        std::cout << query() << "\n";
    }
}

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

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::array<int, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        int v, u, w;
        std::cin >> v >> u >> w;
        v--, u--;
        edges[i] = {v, u, w};
    }
    std::sort(edges.begin(), edges.end(), [&](const std::array<int, 3> &a, const std::array<int, 3> &b) {
        return a[2] < b[2];
    });
    constexpr int INF = 1e9;
    std::vector<int> value(m + 1);
    std::vector<std::vector<std::vector<int>>> dis(m + 1, std::vector<std::vector<int>>(n, std::vector<int>(n, INF)));
    for (int i = 0; i < n; i++) {
        dis[0][i][i] = 0;
    }
    for (auto edge : edges) {
        int v = edge[0], u = edge[1];
        dis[0][v][u] = dis[0][u][v] = 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[0][i][j] = std::min(dis[0][i][j], dis[0][i][k] + dis[0][k][j]);
            }
        }
    }
    int p = 1;
    for (auto edge : edges) {
        int v = edge[0], u = edge[1], w = edge[2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[p][i][j] = std::min({dis[p - 1][i][j], dis[p - 1][i][v] + dis[p - 1][u][j], dis[p - 1][i][u] + dis[p - 1][v][j]});
            }
        }
        value[p++] = w;
    }
    for (int i = 0; i < q; i++) {
        int v, u, k;
        std::cin >> v >> u >> k;
        v--, u--;
        int low = 0, high = m;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (dis[mid][v][u] < k) {
                high = mid;
            } else {
                low = mid;
            }
        }
        std::cout << value[high] << " \n"[i == q - 1];
    }
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using i64 = long long;

struct DSU {
    std::vector<int> p, sz, h;
    
    DSU(int n = 0) : p(n), sz(n, 1), h(n) { 
        std::iota(p.begin(), p.end(), 0); 
    }

    int leader(int x) {
        if (x == p[x]) {
            return x;
        }
        return leader(p[x]);
    }

    bool same(int x, int y) {
        return leader(x) == leader(y);
    }

    bool merge(int x, int y) {
        x = leader(x);
        y = leader(y);
        if (x == y) return false;
        if (h[x] < h[y]) {
            std::swap(x, y);
        }
        if (h[x] == h[y]) {
            ++h[x];
        }
        sz[x] += sz[y];
        p[y] = x;
        return true;
    }

    int size(int x) { 
        return sz[leader(x)]; 
    }
};

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::array<int, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        int v, u, w;
        std::cin >> v >> u >> w;
        v--, u--;
        edges[i] = {v, u, w};
    }
    std::sort(edges.begin(), edges.end(), [&](const std::array<int, 3> &a, const std::array<int, 3> &b) {
        return a[2] < b[2];
    });
    constexpr int INF = 1e9;
    std::vector<int> value(n);
    std::vector<std::vector<std::vector<int>>> dis(n, std::vector<std::vector<int>>(n, std::vector<int>(n, INF)));
    for (int i = 0; i < n; i++) {
        dis[0][i][i] = 0;
    }
    for (auto edge : edges) {
        int v = edge[0], u = edge[1];
        dis[0][v][u] = dis[0][u][v] = 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[0][i][j] = std::min(dis[0][i][j], dis[0][i][k] + dis[0][k][j]);
            }
        }
    }
    int p = 1;
    DSU dsu(n);
    for (auto edge : edges) {
        int v = edge[0], u = edge[1], w = edge[2];
        if (dsu.merge(v, u)) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dis[p][i][j] = std::min({dis[p - 1][i][j], dis[p - 1][i][v] + dis[p - 1][u][j], dis[p - 1][i][u] + dis[p - 1][v][j]});
                }
            }
            value[p++] = w;
        }
    }
    for (int i = 0; i < q; i++) {
        int v, u, k;
        std::cin >> v >> u >> k;
        v--, u--;
        int low = 0, high = n - 1;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (dis[mid][v][u] < k) {
                high = mid;
            } else {
                low = mid;
            }
        }
        std::cout << value[high] << " \n"[i == q - 1];
    }
}

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

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    constexpr int LG = 30;
    std::vector<std::array<i64, 4>> events;
    for (int i = 0; i < n; i++) {
        i64 pow = 1, sum = 0;
        i64 dop = 0;
        for (int j = 0; j < LG; j++) {
            if (i - j < 0) {
                break;
            }
            sum += a[i - j];
            i64 L = dop, R;
            if (i - j == 0) {
                R = 2E18;
            } else {
                i64 x = (pow * 4 - 2) * a[i - j - 1] - sum;
                R = x;
                dop = x;
            }
            pow *= 2;
            events.push_back({L, -1, j, sum});
            events.push_back({R, 1, j, sum});
        }
    }
    for (int i = 0; i < q; i++) {
        int x;
        std::cin >> x;
        events.push_back({x, 0, i, 0});
    }
    std::sort(events.begin(), events.end());
    std::vector<int> ans(q); 
    std::vector<std::multiset<i64>> st(LG);
    for (auto item : events) {
        int h = item[0];
        int o = item[1];
        if (o == -1) {
            int j = item[2];
            i64 sum = item[3];
            st[j].insert(sum);
        } else if (o == 1) {
            int j = item[2];
            i64 sum = item[3];
            st[j].erase(st[j].find(sum));
        } else {
            int i = item[2];
            int low = 0, high = 2E9 + 1;
            while (high - low > 1) {
                int mid = (0LL + low + high) / 2;
                int cur = mid;
                i64 pos = 0;
                bool ok = false;
                for (int cnt = 0; cnt < LG; cnt++) {
                    if (st[cnt].empty()) {
                        continue;
                    }
                    i64 neg = *st[cnt].rbegin();
                    pos += cur;
                    cur = (cur + 1) / 2;
                    if (pos - neg <= h) {
                        ok = true;
                        break;
                    }
                }
                if (ok) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            ans[i] = low;
        }
    }
    for (int i = 0; i < q; i++) {
        std::cout << ans[i] << " \n"[i == q - 1];
    }
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

// Parallel binary search technique optimizes log^3 => log^2
// SegmentTree might be faster then std::multiset
// sl[i] should equals max(a) at the begining cause IDK how to explain but it's obviously important
 
#include <bits/stdc++.h>
#include <algorithm>
 
using namespace std;
using ll = long long;
 
constexpr int W = 31;
constexpr int C = 1'000'000'000;
 
struct Event {
    int x;
    int ind;
    ll s;
 
    bool operator<(const Event& rhs) const { return x < rhs.x; }
};
 
struct SegmentTree {
    int n;
    vector<ll> sgt;
 
    SegmentTree(int n) : n(n), sgt(2 * n, -1) {}
 
    void Change(int i, ll x) {
        for (sgt[i += n] = x; i != 1; i >>= 1) {
            sgt[i >> 1] = max(sgt[i], sgt[i ^ 1]);
        }
    }
 
    int GlobalMax() const { return sgt[1]; }
};
 
vector<int> solve(const vector<int>& a, const vector<int>& q) {
    const int n = a.size(), m = q.size();
 
    vector<ll> ps(n + 1);
    for (int i = 0; i < n; ++i)
        ps[i + 1] = ps[i] + a[i];
 
    vector<ll> min_x(n, 0);
    vector<vector<pair<int, ll>>> change_sum(W);
 
    vector<Event> events;
    events.reserve(2 * n);
    for (int j = 1; j <= W && j <= n; ++j) {
        events.clear();
 
        for (int i = j - 1; i < n; ++i) {
            min_x[i] = max(min_x[i], 1 + ((a[i - j + 1] - 1ll) << (j - 1)));
            ll max_x = i == j - 1 ? 2ll * C : ((ll)a[i - j] << j);
            max_x = min<ll>(max_x, a[i] + C);
 
            if (min_x[i] > max_x) {
                continue;
            }
            const ll xsum = ps[i + 1] - ps[i + 1 - j];
            events.push_back(Event{(int)min_x[i], i, xsum});
            events.push_back(Event{(int)max_x + 1, i, -1});
        }
        sort(events.begin(), events.end());
 
        SegmentTree sgt(n);
        const int k = events.size();
        ll was_max = -1;
 
        for (int i = 0; i < k;) {
            int s = i;
            while (i < k && events[i].x == events[s].x) {
                sgt.Change(events[i].ind, events[i].s);
                ++i;
            }
            ll cur_max = sgt.GlobalMax();
            if (cur_max != was_max) {
                change_sum[j - 1].emplace_back(events[s].x, cur_max);
                was_max = cur_max;
            }
        }
    }
 
    vector<int> sl(m, *max_element(a.begin(), a.end())), sr(m, 2 * C + 1);
 
    vector<int> ord_to_check(m);
    iota(ord_to_check.begin(), ord_to_check.end(), 0);
    for (int iter = 32; iter--;) {
        vector<int> sm(m);
        for (int i = 0; i < m; ++i) {
            sm[i] = sl[i] + (sr[i] - sl[i]) / 2;
        }
        sort(ord_to_check.begin(), ord_to_check.end(), [&](int lhs, int rhs) {
            return sm[lhs] < sm[rhs];
        });
 
        vector<int> ptr(W);
        vector<ll> actual_sum(W, -1);
        for (int i : ord_to_check) {
            const int x = sm[i];
 
 
            ll upper_sum = 0;
            bool nice = false;
            for (int w = 0; w < W; ++w) {
                int& j = ptr[w];
                while (j < change_sum[w].size() && change_sum[w][j].first <= x) {
                    actual_sum[w] = change_sum[w][j++].second;
                }
                upper_sum += 1 + ((x - 1) >> w);
                if (upper_sum - actual_sum[w] <= q[i]) {
                    nice = true;
                }
            }
 
            if (nice) {
                sl[i] = sm[i];
            } else {
                sr[i] = sm[i];
            }
        }
    }
 
    return sl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t = 1;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n), k(q);
        for (int& x : a)
            cin >> x;
        for (int& x : k)
            cin >> x;
 
        auto ans = solve(a, k);
        for (int x : ans)
            cout << x << ' ';
        cout << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;

void solve() {
    int n, m; cin >> n >> m;
    vector<string> v(n);
    for (auto& w : v) cin >> w;

    auto col = [](int x, int y) {
        int c = (x+2*y)%5;
        if (c < 0) c += 5;
        return c;
    };
    auto cell = [&](int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= m) return false;
        return v[x][y] == '#';
    };

    array<vector<pi>, 5> colorings;
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
        if (!cell(i, j)) continue;
        colorings[col(i, j)].emplace_back(i, j);

        for (int di = -1; di <= 1; ++di)
        for (int dj = -1; dj <= 1; ++dj) {
            if (abs(di) + abs(dj) != 1) continue;
            if (!cell(i+di, j+dj)) {
                colorings[col(i+di, j+dj)].emplace_back(i, j);
            }
        }
    }

    auto coloring = colorings[0];
    for (const auto& w : colorings)
        if (w.size() < coloring.size()) coloring = w;
    for (auto [x, y] : coloring) v[x][y] = 'S';
    for (auto line : v) cout << line << '\n';
}

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

    int t; cin >> t;
    while (t--)
        solve();
}

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using ll = long long;

vector<ll> a, lhs, rhs;
vector<int> st;

vector<ll> get_right_out(const vector<ll>& a, vector<ll>& res) {
    const int n = a.size();
    st.clear();
    res.assign(n+1, 0);

    for (int i = 0; i < n; ++i) {
        ll x = a[i] + res[i];
        st.push_back(i);

        while (x != 0) {
            if (st.empty()) {
                const int len = i + 1;
                const ll cnt = x / (len + 1);
                res[i+1] += cnt * len;
                x -= cnt * (len + 1);

                if (x != 0) {
                    res[i+1] += x;
                    st.push_back(x-1);
                    x = 0;
                }
            } else {
                const int j = st.back();
                if (x > i - j) {
                    res[i+1] += i - j;
                    st.pop_back();
                    x -= i - j + 1;
                } else {
                    res[i+1] += x;
                    st.back() += x;
                    x = 0;
                }
            }
        }
    }

    return res;
}

vector<ll> get_left_out(vector<ll>& a, vector<ll>& b) {
    reverse(a.begin(), a.end());
    get_right_out(a, b);
    reverse(b.begin(), b.end());
    reverse(a.begin(), a.end());
    return b;
}

void solve() {
    int n; cin >> n;
    
    a.resize(n);
    for (ll& x : a) cin >> x;

    get_right_out(a, lhs);
    get_left_out(a, rhs);

    ll ans = 0;
    for (int i = 0; i < n; ++i)
        cout << lhs[i] + a[i] + rhs[i+1] << ' ';
    cout << '\n';
}

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

    int t = 1;
    cin >> t;
    while (t--) solve();
}

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    int p = (n + 1) / 2 - 1;
    int res = std::count(a.begin() + p, a.end(), a[p]);
    std::cout << res << "\n";
}

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

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P = 1e9 + 7;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int S = 0, sum = 0;
    int cur = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        cur += a[i];
        cur = max(cur, 0LL);
        S = max(S, cur);
    }
    sum = (sum % P + P) % P;
    S = S % P;
    int t = 1;
    for (int i = 0; i < k; i++) {
        t = t * 2 % P;
    }
    int ans = (sum + S * t - S + P) % P;
    cout << ans << '\n';
}


signed main() {
    //cout << fixed << setprecision(20);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1, G = 1;
    //cin >> G;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

#include <bits/stdc++.h>
 
using i64 = long long;
 
void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++) {
        int v, u;
        std::cin >> v >> u;
        --v, --u;
        adj[v].emplace_back(u);
        adj[u].emplace_back(v);
    }
    auto check = [&](int x) {
        int res = 0;
        auto dfs = [&](auto self, int v, int f) -> int {
            int sz = 1;
            for (int u : adj[v]) {
                if (u == f) {
                    continue;
                }
                sz += self(self, u, v);
            }
            if (sz >= x && f != v) {
                ++res, sz = 0;
            }
            return sz;
        };
        int t = dfs(dfs, 0, 0);
        return (res > k || (t >= x && res == k) ? true : false);
    };
    int low = 1, high = n / (k + 1) + 1;
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    std::cout << low << "\n";
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
#define int ll
#define all(a) a.begin(), a.end()
 
void solve() {
    int n, x;
    cin >> n >> x;
    ++x;
    vector<int> a(n);
    for (int &i: a)
        cin >> i;
    int res = -1;
    for (int i = 30; i >= 0; --i) {
        vector<int> b;
        bool open = false;
        for (int j = 0; j < a.size(); ++j) {
            if (!open)
                b.push_back(a[j]);
            else
                b.back() ^= a[j];
            if (a[j] & (1 << i))
                open = !open;
        }
        if (!(x & (1 << i))) {
            if (open) {
                cout << res << '\n';
                return;
            }
            a = b;
        } else {
            if (!open)
                res = max(res, (int) b.size());
        }
    }
    cout << res << '\n';
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
int const maxn = 1e5 + 5;
int a[maxn];
 
int solve(int n, int x) {
    int res = 0, curr = 0;
    for (int i = 1; i <= n; i++) {
        curr ^= a[i];
        if ((curr|x) == x) curr = 0, res++;
        else {
            if (i == n) return -1;
        }
    }
    return res;
}
 
main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        for (int i = 1; i <= n; i++) cin >> a[i];
        int ans = -1;
        ans = max(ans, solve(n, x));
        for (int b = 29; b >= 0; b--) {
            if ((x>>b)&1) {
                int y = (x^(1 << b));
                for (int c = b - 1; c >= 0; c--) {
                    if (((y>>c)&1) == 0) y ^= (1 << c);
                }
                ans = max(ans, solve(n, y));
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
 
using i64 = long long;
 
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
 
template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % P)} {}
    
    constexpr int norm(int x) const {
        if (x < 0) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(P - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    constexpr MInt &operator*=(MInt rhs) {
        x = 1LL * x * rhs.x % P;
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
 
constexpr int MOD = 1e9 + 7;
using Z = MInt<MOD>;
 
namespace comb {
    int n = 0;
    std::vector<Z> _fac = {1};
    std::vector<Z> _invfac = {1};
    std::vector<Z> _inv = {0};
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int m, int k) {
        if (m < k || k < 0) return 0;
        return fac(m) * invfac(k) * invfac(m - k);
    }
} // namespace comb
 
void solve() {
    int n, m1, m2;
    std::cin >> n >> m1 >> m2;
    std::vector<int> p(m1), s(m2);
    for (int i = 0; i < m1; i++) {
        std::cin >> p[i];
    }
    for (int i = 0; i < m2; i++) {
        std::cin >> s[i];
    }
    if (p[0] != 1 || s[0] != p[m1 - 1] || s[m2 - 1] != n) {
        std::cout << "0\n";
        return;
    }
    Z res = comb::binom(n - 1, s[0] - 1);
    for (int i = m1 - 2; i > -1; i--) {
        res *= comb::binom(p[i + 1] - 2, p[i + 1] - p[i] - 1) * comb::fac(p[i + 1] - p[i] - 1);
    }
    for (int i = 1; i < m2; i++) {
        res *= comb::binom(n - s[i - 1] - 1, s[i] - s[i - 1] - 1) * comb::fac(s[i] - s[i - 1] - 1);
    }
    std::cout << res << "\n";
}
 
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    #ifndef ONLINE_JUDGE
        freopen("/home/q1n/coding/input.txt", "r", stdin);
        freopen("/home/q1n/coding/output.txt", "w", stdout);
    #else
        // online submission
    #endif
 
    int t = 1;
    std::cin >> t;
 
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using i64 = long long;

template<class Info>
struct Fenwick {
    std::vector<Info> t;
    int n;
    
    Fenwick(int n = 0) : n(n) {
        t.resize(n);
    }
    
    void add(int x, const Info &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            t[i - 1] = t[i - 1] + v;
        }
    }
    
    Info sum(int x) {
        x++;
        Info res = Info();
        for (int i = x; i > 0; i -= i & -i) {
            res = res + t[i - 1];
        }
        return res;
    }
    
    Info rangeSum(int l, int r) {
        Info res = sum(r) - sum(l - 1);
        return res;
    }
};

void solve() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n), pos(n + 1);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::reverse(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        pos[a[i]] = i;
    }
    constexpr int K = 19;
    std::vector<i64> res(q);
    std::vector<std::vector<std::pair<int, int>>> qry(n);
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        l--, r--;
        std::swap(l, r);
        l = n - l - 1;
        r = n - r - 1;
        qry[r].emplace_back(l, i);
    }
    std::vector<i64> dp(n + 1);
    Fenwick<i64> f(n);
    for (int r = 0; r < n; r++) {
        int x = a[r];
        dp[x] = 1;
        // n * log(n) * log(n)
        for (int y = x; y <= n; y += x) {
            if (pos[y] > pos[x]) {
                continue;
            }
            for (int z = 2 * y; z <= n; z += y) {
                if (pos[z] > pos[y]) {
                    continue;
                }
                dp[z] += dp[y];
            }
        }
        // n * log(n) * log(n)
        for (int y = x; y <= n; y += x) {
            f.add(pos[y], dp[y]);
            dp[y] = 0;
        }
        // q * log(n)
        for (auto [l, i] : qry[r]) {
            res[i] += f.rangeSum(l, r);
        }
    }
    for (int i = 0; i < q; i++) {
        std::cout << res[i] << " \n"[i == q - 1];
    }
}

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

    int t = 1;
    std::cin >> t;

    while (t--) {
        solve();
    }
}