#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();
}