#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int it = 0; it < t; ++it) {
        int a, b;
        cin >> a >> b;
        cout << (a == 0 ? 1 : a + 2 * b + 1) << '\n';
    }
    return 0;
}

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort()
    if n == 1:
        if a[0] > 1:
            print("NO")
        else:
            print("YES")
        continue
    if a[-2] + 1 < a[-1]:
        print("NO")
    else:
        print("YES")

#include<bits/stdc++.h>
using namespace std;
int sz = 26;
 
void solve(){
    string s;
    cin >> s;
    int m = 0, n = (int)s.size();
    vector<bool>prev(sz, false);
    for(auto &i : s){
        if(prev[i - 'a']){
            m += 2;
            for(int j = 0; j < sz; j++) prev[j] = false;
        }
        else prev[i - 'a'] = true;
    }
 
    cout << n - m << endl;
}
 
int main(){
    int t;
    cin >> t;
    while (t--){
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
 
 
void solve() {
    int n; cin >> n;
    vector<int> a(n);
 
    forn(i, n) 
        cin >> a[i];
    int ans = 0;
    int ap = n, as = 0;
    for(int i = 0, l = -1; i <= n; i++) {
        if (i == n || a[i] == 0) {
            int cnt = 0;
            bool neg = false;
            int left = -1, right = -1;
            int cl = 0, cr = 0;
            for (int j = l+1; j < i; j++) {
                neg ^= a[j] < 0;
                if (a[j] < 0) {
                    right = j;
                    cr = 0;
                }
 
                if (abs(a[j]) == 2) {
                    cnt++, cr++;
                    if (left == -1) cl++;
                }
 
                if (a[j] < 0 && left == -1) {
                    left = j;
                }
            }
            if (neg) {
                if (cnt - cl > cnt - cr) {
                    right = i;
                    cnt -= cl;
                } else {
                    left = l;
                    cnt -= cr;
                }
            } else {
                left = l, right = i;
            }
            if (ans < cnt) {
                ans = cnt;
                ap = left + 1, as = n - right;
            }
 
            l = i;
        }
    }
    cout << ap << ' ' << as << endl;
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
 
const int INF = INT_MAX >> 1;
 
void solve() {
    int n; cin >> n;
    int cnt1 = 0;
    vector<int> cnt (n, 0);
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0, k = (n - i) % n; j < n; j++, k = (k + 1 == n ? 0 : k + 1)) if (s[j] == '1') {
            cnt1++;
            cnt[k]++;
        }
    }
    int ans = INF;
    for (int i = 0; i < sz(cnt); i++) {
        ans = min(ans, cnt1 - cnt[i] + (n - cnt[i]));
    }
    cout << ans << endl;
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        solve();
    }
}

tst = int(input())
for _ in range(tst):
    n = int(input())
    s = input()
    b = [0 for i in range(n+1)]
    bal = n
    b[0] = bal
    ans = 0
    for i in range(1,n+1):
        if s[i-1] == '+':
            bal += 1
        else:
            bal -= 1
        b[i] = bal
        for j in range(i):
            if b[j] >= b[i] and (b[j] - b[i]) % 3 == 0:
                ans += 1
    print(ans)

tst = int(input())
for _ in range(tst):
    n = int(input())
    s = input()
    f = [0 for i in range(3)]
    cur_bal = n
    cnt_bal = [0 for i in range(2 * n + 1)]
    cnt_bal[cur_bal] += 1
    f[cur_bal % 3] += 1
    ans = 0
    for i in range(n):
        #print(f)
        #print(cur_bal, ans)
        new_bal = cur_bal
        if s[i] == '-':
            new_bal -= 1
            f[new_bal % 3] += cnt_bal[new_bal]
            ans += f[new_bal % 3]
            cnt_bal[new_bal] += 1
            f[new_bal % 3] += 1
        else:
            f[new_bal % 3] -= cnt_bal[new_bal]
            new_bal += 1
            ans += f[new_bal % 3]
            cnt_bal[new_bal] += 1
            f[new_bal % 3] += 1
        cur_bal = new_bal
    print(ans)

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        string s;
        cin >> s;
        bool ok = true;
        if (s.length() % 2 == 0) {
            forn(i, s.length() / 2)
                if (s[i] != s[i + s.length() / 2])
                    ok = false;
        } else
            ok = false;
        cout << (ok ? "YES" : "NO") << endl;
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        set<int> a;
        for (int i = 1; i * i <= n; i++)
            a.insert(i * i);
        for (int i = 1; i * i * i <= n; i++)
            a.insert(i * i * i);
        cout << a.size() << endl;
    }
}

#include<bits/stdc++.h>
#define len(s) (int)s.size()
using namespace std;
using ll = long long;
 
void solve(){
    ll a, s;
    cin >> a >> s;
    vector<int>b;
    while(s){
        int x = a % 10;
        int y = s % 10;
        if(x <= y) b.emplace_back(y - x);
        else{
            s /= 10;
            y += 10 * (s % 10);
            if(x < y && y >= 10 && y <= 19) b.emplace_back(y - x);
            else{
                cout << -1 << '\n';
                return;
            }
        }
        a /= 10;
        s /= 10;
    }
    if(a) cout << -1 << '\n';
    else{
        while (b.back() == 0) b.pop_back();
        for(int i = len(b) - 1; i >= 0; i--) cout << b[i];
        cout << '\n';
    }
}
 
int main(){
    ios_base ::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t){
        solve();
        t--;
    }
    return 0;
}

//
// Created by Vlad on 17.12.2021.
//
 
#include <bits/stdc++.h>
 
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
*/
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(143);
 
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
 
int n, m;
vector<vector<int>> p;
 
bool check(int x){
    vector<bool> abl(m);
    bool pair = false;
    for(int i = 0; i < n; ++i){
        int c = 0;
        for(int j = 0; j < m; ++j){
            if(p[i][j] >= x){
                abl[j] = true;
                c++;
            }
        }
        if(c > 1) pair = true;
    }
    if(!pair && m > 1) return false;
    bool ans = true;
    for(bool b: abl){
        ans = ans && b;
    }
    return ans;
}
 
void solve() {
    cin >> n >> m;
    p.assign(n, vector<int>(m));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> p[i][j];
        }
    }
    int l = 1, r = 2;
    while (check(r)) r *= 2;
    while (r - l > 1){
        int mid = (r + l) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l;
}
 
bool multi = true;
 
signed main() {
    //freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (; t != 0; --t) {
        solve();
        cout << "\n";
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
const int MAX_N = 2e5;
 
int main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;
        vector<int> a(n), cnt(n + 1);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            cnt[a[i]]++;
        }
        sort(a.begin(), a.end());
        stack<int> st;
        vector<ll> ans(n + 1, -1);
        ll sum = 0;
        for (int i = 0; i <= n; ++i) {
            if (i > 0 && cnt[i - 1] == 0) {
                if (st.empty()) {
                    break;
                }
                int j = st.top();
                st.pop();
                sum += i - j - 1;
            }
            ans[i] = sum + cnt[i];
            while (i > 0 && cnt[i - 1] > 1) {
                cnt[i - 1]--;
                st.push(i - 1);
            }
        }
        for (ll x : ans) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> p(n);
        forn(i, n)
            p[i] = i;
        if (tt > 0)
            cout << endl;
        forn(round, k) {
            int index = 0;
            forn(table, m) {
                int size = n / m;
                if (table < n % m)
                    size++;
                cout << size;
                forn(j, size)
                    cout << " " << p[index++] + 1;
                cout << endl;                        
            }
            rotate(p.begin(), p.begin() + (n % m) * ((n + m - 1) / m), p.end());
        }
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int k;
 
map <int, vector<int>> mx;
map <int, vector<int>> my;
map <pair<int ,int>, bool> used;
map <pair<int, int>, int> time_of;
 
int dfs(int x, int y) {
    used[{x, y}] = true;
    int _min_ = time_of[{x, y}];
 
    auto i = lower_bound(mx[x].begin(), mx[x].end(), y);
    auto j = lower_bound(my[y].begin(), my[y].end(), x);
 
    if (++i != mx[x].end() && !used[{x, *i}] && abs(*i - y) <= k) {
        _min_ = min(_min_, dfs(x, *i));
    }
    --i;
    if (i != mx[x].begin() && !used[{x, *(--i)}] && abs(*i - y) <= k) {
        _min_ = min(_min_, dfs(x, *i));
    }
 
    if (++j != my[y].end() && !used[{*j, y}] && abs(*j - x) <= k) {
        _min_ = min(_min_, dfs(*j, y));
    }
    --j;
    if (j != my[y].begin() && !used[{*(--j), y}] && abs(*j - x) <= k) {
        _min_ = min(_min_, dfs(*j, y));
    }
 
    return _min_;
}
 
void solve() {
    mx.clear();
    my.clear();
    used.clear();
 
    int n;
    cin >> n >> k;
    vector <pair<int, int>> a(n);
    int x, y, timer;
 
    for (int i = 0; i < n; ++i) {
        cin >> x >> y >> timer;
        a[i] = {x, y};
        time_of[{x, y}] = timer;
        mx[x].push_back(y);
        my[y].push_back(x);
    }
    vector<int> res;
 
    for (auto now: mx) {
        sort(mx[now.first].begin(), mx[now.first].end());
    }
    for (auto now: my) {
        sort(my[now.first].begin(), my[now.first].end());
    }
 
    for (auto now: a) {
        if (!used[now]) {
            res.push_back(dfs(now.first, now.second));
        }
    }
    sort(res.begin(), res.end());
 
    int ans = res.size() - 1;
    for (int i = 0; i < res.size(); ++i) {
        ans = min(ans, max((int)res.size() - i - 2, res[i]));
    }
    cout << ans << '\n';
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int tests;
    cin >> tests;
    forn(tt, tests) {
        solve();
    }
}

#include <bits/stdc++.h>
//#define int long long
#define ld long double
#define x first
#define y second
#define pb push_back
 
using namespace std;
const int Q = 100;
 
int n, q, p[100005], r[100005], a[100005];
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> q;
 
    for(int i = 0; i < n; i++)
    {
        cin >> p[i];
        p[i]--;
    }
 
    for(int i = 0; i < n; i++)
        r[p[i]] = i;
 
    for(int i = 0; i < n; i++)
    {
        int x = i;
 
        for(int j = 0; j < Q; j++)
            x = p[x];
 
        a[i] = x;
    }
 
    while(q--)
    {
        int t, x, y;
        cin >> t >> x >> y;
 
        if(t == 2)
        {
            x--;
 
            while(y >= Q)
            {
                y -= Q;
                x = a[x];
            }
 
            while(y--)
                x = p[x];
 
            cout << x + 1 << "\n";
        }
        else
        {
            x--;
            y--;
 
            swap(r[p[x]], r[p[y]]);
            swap(p[x], p[y]);
 
            int ax = x;
 
            for(int i = 0; i < Q; i++)
                ax = p[ax];
 
            int x2 = x;
 
            for(int i = 0; i < Q; i++)
            {
                a[x] = ax;
                x = r[x];
                ax = r[ax];
            }
 
            swap(x, y);
 
            ax = x;
 
            for(int i = 0; i < Q; i++)
                ax = p[ax];
 
            x2 = x;
 
            for(int i = 0; i < Q; i++)
            {
                a[x] = ax;
                x = r[x];
                ax = r[ax];
            }
        }
    }
}

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        string n;
        cin >> n;
        if((n.back() - '0') % 2 == 0) {
            cout << "0\n";
            continue;
        }
        if((n[0] - '0') % 2 == 0) {
            cout << "1\n";
            continue;
        }
        int count_2 = count(n.begin(), n.end(), '2');
        int count_4 = count(n.begin(), n.end(), '4');
        int count_6 = count(n.begin(), n.end(), '6');
        int count_8 = count(n.begin(), n.end(), '8');
        if(count_2 > 0 || count_4 > 0 || count_6 > 0 || count_8 > 0) {
            cout << "2\n";
            continue;
        }
        cout << "-1\n";
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
void solve() {
    ll a, b;
    cin >> a >> b;
    cout << min(min(a, b), (a + b) / 4) << '\n';
}
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        if (a[0] != n && a[n - 1] != n)
            cout << -1 << endl;
        else {
            for (int i = n - 1; i >= 0; i--)
                cout << a[i] << " ";
            cout << endl;
        }
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
void solve(){
    int n;
    cin >> n;
    vector<int> b(n + 1), p(n + 1), dist(n + 1, -1);
 
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    for(int i = 1; i <= n; i++)
        cin >> p[i];
 
    if (b[p[1]] != p[1]){
        cout << -1 << '\n';
        return;
    }
 
    dist[p[1]] = 0;
    for(int i = 2; i <= n; i++){
        if(dist[b[p[i]]] == -1){
            cout << -1 << '\n';
            return;
        }
        dist[p[i]] = dist[p[i - 1]] + 1;
    }
 
    for(int i = 1; i <= n; i++) {
        cout << dist[i] - dist[b[i]] << ' ';
    }
    cout << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while(t-- > 0) {
        solve();
    }
}

//
// Created by Vlad on 16.11.2021.
//
 
#include <bits/stdc++.h>
 
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(143);
 
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
 
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> color(n, -1);
    deque<int> q;
    for(int i = 0; i < k; ++i){
        int x;
        cin >> x;
        color[--x] = 0;
        q.push_back(x);
    }
    color[0] = 1;
    q.push_back(0);
    vector<vector<int>> g(n);
    for(int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    while(!q.empty()){
        int v = q.front();
        q.pop_front();
        for(int u: g[v]){
            if(color[u] == -1){
                color[u] = color[v];
                q.push_back(u);
            }
        }
    }
    for(int v = 1; v < n; ++v){
        if(g[v].size() == 1 && color[v] == 1){
            cout << "YES";
            return;
        }
    }
    cout << "NO";
}
 
bool multi = true;
 
signed main() {
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (; t != 0; --t) {
        solve();
        cout << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
 
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
*/
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(143);
 
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
 
vector<vector<int>> sl;
vector<int> nearest;
 
int count(int v, int dist, int p = -1){
    bool children = true;
    int s = 0;
    for(int u: sl[v]){
        if(u == p) continue;
        int c = count(u, dist + 1, v);
        if(c < 0) children = false;
        nearest[v] = min(nearest[v], nearest[u] + 1);
        s += c;
    }
    if(nearest[v] <= dist) return 1;
    if(s == 0 || !children) return -1;
    return s;
}
 
void solve() {
    int n, k;
    cin >> n >> k;
    sl.assign(n, vector<int>(0));
    nearest.assign(n, n);
    for(int i = 0; i < k; ++i){
        int x;
        cin >> x;
        --x;
        nearest[x] = 0;
    }
    for(int i = 1; i  < n; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        sl[u].emplace_back(v);
        sl[v].emplace_back(u);
    }
    cout << count(0, 0);
}
 
bool multi = true;
 
signed main() {
    //freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    /*ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);*/
    int t = 1;
    if (multi) {
        cin >> t;
    }
    for (; t != 0; --t) {
        solve();
        cout << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define forn(i, n) for (int i = 0; i < int(n); i++)

vector<ll> t, a;
ll s, tl;

const ll MAX = 1'000'000'000'000'000LL;

void build(int v, int l, int r) {
	if (l == r)
		t[v] = a[l];
	else {
		int m = (l + r) / 2;
		build (v * 2, l, m);
		build (v * 2 + 1, m + 1, r);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
}

void update(int v, int l, int r) {
	if (l == r)
		t[v] = MAX;
	else {
		int m = (l + r) / 2;
		if (tl <= m)
			update(v * 2, l, m);
		else
			update(v * 2 + 1, m + 1, r);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
	}
}

int lower_bound_s(int v, int l, int r) {
	if (r < tl || (l == r && s < -t[v])) {
		return -1;
	}
    if (l == r || -t[v] <= s) {
        return r;
    }
	int m = (l + r) / 2;

	if (m < tl) {
        return lower_bound_s(2 * v + 1, m + 1, r);
	}
	if (s < -t[2 * v]) {
        return lower_bound_s(2 * v, l, m);
	}
	int res = lower_bound_s(2 * v + 1, m + 1, r);
	return (res == -1) ? m : res;
}


int main() {
    int tests;
    cin >> tests;
    forn(tt, tests) {
        int n;
        cin >> n >> s;
        t = vector<ll>(4 * n);
        a = vector<ll>(n);
        forn(i, n) {
            cin >> a[i];
        }
        for (int i = 1; i < n; ++i) {
            a[i] += a[i - 1];
        }
        build(1, 0, n - 1);
        int first = -1, second = -2;
        for (tl = 0; tl < n; ++tl) {
            int v = lower_bound_s(1, 0, n - 1);
            if (v != -1 && v - tl > second - first) {
                first = tl + 1;
                second = v + 1;
            }
            s -= a[tl];
            if (tl != 0) s += a[tl - 1];
            update(1, 0, n - 1);
        }
        if (first == -1) {
            cout << -1;
        } else {
            cout << first << " " << second;
        }
        cout << endl;
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
 
const int N = 1e6 + 50;
string a[N];
 
int n,m;
int ans;
 
void solve(int sum0) {
    vector<int> v;
    for (int sum = sum0, ad = 0, pref = 0; sum < n + m; sum += 2, ad++) {
        vector<int> cur;
        int li = max(0, sum - m + 1), ri = min(n - 1, sum);
        if (li > ri) continue;
 
        for (int i = li; i <= ri; i++) {
            int j = sum - i;
 
            if (a[i][j] == '1')
                cur.emplace_back(i);
        }
 
        while (pref != sz(v) && v[pref] + ad > ri) {
            pref++;
        }
        for (int i = pref; i < sz(v); i++) {
            int new_val = v[i];
            while (!cur.empty() && cur.back() - ad >= v[i]) {
                new_val = max(new_val, cur.back() - ad);
                cur.pop_back();
            }
            v[i] = new_val;
        }
        if (!cur.empty()) {
            v.emplace_back(cur.back() - ad);
            ans++;
        }
    }
}
 
int main() {
    int t;
    cin >> t;
 
    forn(tt, t) {
        cin >> n >> m;
 
        forn(i, n) {
            string s; 
            cin >> a[i];
        }
 
        ans = 0;
        solve(0);
        solve(1);
        
        cout << ans << '\n';
    }
}