#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T --> 0) {
        string n;
        cin >> n;
        if (n.size() == 2) {
            cout << n[1] << '\n';
        } else {
            cout << *min_element(n.begin(), n.end()) << '\n';
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << a + b + c << " " << b + c << " " << c << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve(vector<vector<int>> &a) {
    int n = a.size(), m = a[0].size();
    vector<int> bad;
    for (int i = 0; i < n && bad.empty(); i++) {
        vector<int> b = a[i];
        sort(b.begin(), b.end());
        for (int j = 0; j < m; j++) {
            if (a[i][j] != b[j]) bad.push_back(j);
        }
    }
    if ((int)bad.size() == 0) {
    	cout << 1 << " " << 1 << "\n";
    	return;
    }
    if ((int)bad.size() > 2) {
    	cout << -1 << "\n";
    	return;
    }
    for (int i = 0; i < n; i++) {
        swap(a[i][bad[0]], a[i][bad[1]]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (a[i][j] < a[i][j - 1]) {
            	cout << -1 << "\n";
            	return;
           	}
        }
    }
    cout << bad[0] + 1 << " " << bad[1] + 1 << "\n";
    return;
}

int main() {
	#ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> a(n, vector<int>(m));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> a[i][j];
			}
		}
		solve(a);
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

void solve() {
    int n, k;
    cin >> n >> k;
    long long ans = 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        ans += a[i];
        a[i] += i + 1;
    }
    sort(all(a));
    reverse(all(a));
    for (int i = 0; i < k; i++) ans -= a[i];
    for (int i = 0; i < k; i++) {
        ans += n;
        ans -= i;
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>

const int INF = 1e9 + 1;
const ll INFLL = 1e18;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &c : a) cin >> c;
    map<int, int> cnt;
    for (auto &c : a) cnt[c]++;
    set<pii> s1, s2;
    int sum1 = 0;
    for (auto &c : cnt) s2.insert(mp(c.se, c.fi));
    int ans = INF;
    int skip = 0;
    for (int x = 0; x <= n; x++) {
        if (s1.find(mp(cnt[x - 1], x - 1)) != s1.end()) {
            sum1 -= cnt[x - 1];
            s1.erase(mp(cnt[x - 1], x - 1));
        }
        if (s2.find(mp(cnt[x - 1], x - 1)) != s2.end()) {
            s2.erase(mp(cnt[x - 1], x - 1));
        }
        while (s2.size() && sum1 + s2.begin()->fi <= k) {
            s1.insert(*s2.begin());
            sum1 += s2.begin()->fi;
            s2.erase(s2.begin());
        }
        if (k < skip) break;
        int now = x + s2.size();
        if (x == 0) {
            now = max(1, (int)s2.size());
        }
        ans = min(ans, now - x);
        if (cnt[x] == 0) skip++;
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>

const int INF = 1e9 + 1;
const ll INFLL = 1e18;

vector<int> f;

void incr(int x, int d) {
    for (; x < (int)f.size(); x |= (x + 1)) f[x] = max(f[x], d);
}

int get(int x) {
    int ans = -1;
    for (; x >= 0; x = (x & (x + 1)) - 1) ans = max(ans, f[x]);
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &c : a) cin >> c;
    map<int, vector<int>> gist;
    for (int i = 0; i < n; i++) gist[a[i]].pb(i);
    vector<pii> seg(m);
    f.assign(n, -1);
    for (auto &c : seg) {
        cin >> c.fi >> c.se; c.fi--; c.se--;
        incr(c.fi, c.se);
    }
    vector<int> mnl(n);
    set<int> s;
    int l = n;
    for (int r = n - 1; r >= 0; r--) {
        while (l - 1 >= 0 && !s.count(a[l - 1])) {
            l--;
            s.insert(a[l]);
        }
        mnl[r] = l;
        s.erase(a[r]);
    }
    int mnr = -1;
    for (auto &c : seg) {
        int l = c.fi, r = c.se;
        if (mnl[r] <= l) continue;
        mnr = max(mnr, mnl[r] - 1);
    }
    if (mnr == -1) {
        cout << 0 << "\n";
        return;
    }
    int ans = mnr + 1;
    for (int l = 0; l + 1 < n; l++) {
        if (gist[a[l]][0] != l) {
            int id = lower_bound(all(gist[a[l]]), l) - gist[a[l]].begin() - 1;
            int pr = gist[a[l]][id];
            if (get(pr) >= l) {
                break;
            }
        }
        int id = upper_bound(all(gist[a[l]]), mnr) - gist[a[l]].begin();
        if (id != (int)gist[a[l]].size()) {
            int nxt = gist[a[l]][id];
            if (get(l) >= nxt) {
                mnr = nxt;
            }
        }
        mnr = max(mnr, l + 1);
        ans = min(ans, mnr - l);
    }
    cout << ans << "\n";
}

int main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define pb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pii pair<int, int>
#define puu pair<unsigned, unsigned>
#define ll long long
#define mp make_pair
#define ui unsigned
#define ull unsigned long long
#define ld double
#define pld pair<ld, ld>
#define pll pair<ll, ll>
#define int ll

const int INF = 1e9 + 1;
const ll INFLL = 1e18;
 
vector<vector<int>> g;
vector<int> with;
vector<int> usd;
 
int dfs(int v) {
    if (usd[v]) return 0;
    usd[v] = 1;
    for (auto &to : g[v]) {
        if (with[to] == -1) {
            with[to] = v;
            return 1;
        }
    }
    for (auto &to : g[v]) {
        if (dfs(with[to])) {
            with[to] = v;
            return 1;
        }
    }
    return 0;
}

signed main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif
    int n, A;
    cin >> n >> A;
    vector<int> a(n);
    vector<int> l, r;
    for (auto &c : a) {
        cin >> c;
        if (3 * c > A) {
            l.pb(c);
        } else {
            r.pb(c);
        }
    }
    g.resize(l.size());
    with.resize(r.size(), -1);
    for (int i = 0; i < (int)l.size(); i++) {
        for (int j = 0; j < (int)r.size(); j++) {
            if (l[i] % r[j] == 0 && 2 * l[i] + r[j] <= A) {
                g[i].pb(j);
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < (int)l.size(); i++) {
        usd.assign(l.size(), 0);
        cnt += dfs(i);
    }
    if (cnt < (int)l.size()) {
        cout << -1;
        return 0;
    }
    vector<pii> ans;
    for (int j = 0; j < (int)r.size(); j++) {
        if (with[j] == -1) {
            ans.pb(3 * r[j], 2 * r[j]);
        } else {
            ans.pb(2 * l[with[j]] + r[j], l[with[j]] + r[j]);
        }
    }
    cout << ans.size() << "\n";
    for (auto &c : ans) cout << c.fi << " " << c.se << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6;
int g[MAXN + 1];
string s;

vector<pair<int, int>> segments; // [l, r]

int get(int k, int i) { // get k-th '1' on [i, |s|)
	--i;
	while (k --> 0) i = s.find('1', i + 1);
	return i;
}

void five() {
	int first = get(1, 0), last = get(5, 0);
	int r = (int)s.size() - 1;
	if (last - first + 1 == 5) { // creating 16: ['001111', '1', '0000']
		segments.emplace_back(0, last - 1);
		segments.emplace_back(last, last);
		if (last < r) segments.emplace_back(last + 1, r);
	} else { // creating 8: cut out '101' or '100' and cut everything in single digits
		int pos = s.find("101");
		if (pos == string::npos) pos = s.find("100");
		for (int i = 0; i < pos; ++i) segments.emplace_back(i, i);
		segments.emplace_back(pos, pos + 2);
		for (int i = pos + 3; i <= r; ++i) segments.emplace_back(i, i);
	}
}

void solve(int l, int r, int k, int n) { // [l; r]
	if (k == n) { // cutting into single digits
		for (int i = l; i <= r; ++i) segments.emplace_back(i, i);

	} else if (k == 2 && n == 3) {
		int pos = get(1, l);
		if (s[pos + 1] == '1') { // ['11', '00...00']
			segments.emplace_back(l, pos + 1);
			if (pos + 2 <= r) segments.emplace_back(pos + 2, r);

		} else { // ['10', '0001', '00000']
			int newpos = get(1, pos + 1);
			segments.emplace_back(l, pos + 1);
			segments.emplace_back(pos + 2, newpos);
			if (newpos + 1 <= r) segments.emplace_back(newpos + 1, r);
		}

	} else if (3 * k / 2 >= n) { // using previous if technique
		int pos = get(2, l);
		solve(l, pos, 2, 3);
		if (k > 2) solve(pos + 1, r, k - 2, n - 3);

	} else if ((k == 4 && n == 8) || (k == 9 && n == 16)) {
		int pos = get(1, l);
		string sub = s.substr(pos, 3);
		segments.emplace_back(l, pos + 2);
		if (sub == "100") solve(pos + 3, r, k - 1, n - 4);
		if (sub == "101") solve(pos + 3, r, k - 2, n - 5);
		if (sub == "110") solve(pos + 3, r, k - 2, n - 6);
		if (sub == "111") solve(pos + 3, r, k - 3, n - 7);

	} else if ((k == 7 && n == 11) || (k == 10 && n == 16)) {
		int mid = get(4, l);
		solve(l, mid, 4, 8);
		solve(mid + 1, r, k - 4, n - 8);

	} else { // common case
		int mid = get(k / 2, l);
		solve(l, mid, k / 2, n / 2);
		solve(mid + 1, r, k - k / 2, n / 2);

	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	g[1] = 1;
	for (int i = 2; i <= MAXN; ++i) g[i] = g[(i + 1) / 2] * 2;
	int T;
	cin >> T;
	while (T --> 0) {
		cin >> s;
		int k = count(s.begin(), s.end(), '1');
		if (!k) {
			cout << -1 << '\n';
			continue;
		}
		segments.clear();
		if (k == 5) five();
		else solve(0, (int)s.size() - 1, k, g[k]);
		cout << segments.size() << '\n';
		for (auto &[l, r] : segments) {
			cout << l + 1 << ' ' << r + 1 << '\n';
		}
	}
	return 0;
}

В данной задаче достаточно вывести $$$n - 3$$$, $$$1$$$, $$$1$$$, $$$1$$$. Нетрудно убедиться, что этот ответ подходит для любого $$$n \ge 4$$$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T --> 0) {
        int n;
        cin >> n;
        cout << n - 3 << ' ' << 1 << ' ' << 1 << ' ' << 1 << '\n';
    }
    return 0;
}

Будем действовать жадно. Найдём элемент в исходной версии, который встречается чаще всех. Пусть этот элемент равен $$$x$$$ и он встречается $$$k$$$ раз. Тогда сделаем такую версию массива, в которой все элементы равны $$$x$$$. Для этого создадим копию данного массива, сложим все элементы, равные $$$x$$$, в один массив. Теперь повторим все действия с новой версией массива. Так продолжим до тех пор, пока не получим версию из $$$n$$$ элементов, равных $$$x$$$.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T --> 0) {
        int n;
        cin >> n;
        map<int, int> q;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            ++q[x];
        }
        int am = 0;
        for (auto &[x, y] : q) {
            am = max(am, y);
        }
        int ans = 0;
        while (am < n) {
            int d = min(n - am, am);
            ans += 1 + d;
            am += d;
        }
        cout << ans << '\n';
    }
    return 0;
}

Сначала заметим, что для любых двух различных вершин их дети независимы. Это значит, что инфекция не может распространяться между детьми двух различных вершин. Также неважно, как инфекция распространяется среди детей одной вершины, поэтому нам достаточно знать только количество вершин с одинаковым родителем.

Используя эти знания мы можем свести данную задачу к следующей: Дан массив из $$$k$$$ положительных целых чисел, где каждое число означает количество здоровых вершин с одинаковым родителем. Каждую секунду можно выбрать одно число в этом массиве и заразить его (с помощью инъекции). Также каждую секунду все заражённые числа уменьшаются на 1 (из-за распространения).

Для решения этой задачи используем жадный алгоритм. Отсортируем массив в порядке убывания и заразим все числа по порядку. Эти инъекции необходимы, потому что числа независимы. После этого каждую секунду все числа будут уменьшаться на 1, причём мы можем выбрать ровно одно число, которое будет уменьшено дополнительно на 1 (инъекцией). Этим числом должен быть выбран максимум в массиве.

Эта задача может быть решена симуляцией процесса, потому что сумма чисел в этом массиве изначально равна $$$n$$$.

#include <bits/stdc++.h>
using namespace std;

int ans;

void proc(vector<int>& a) {
    if (a.empty()) return;
    int n = a.size();
    int last = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == a[0]) {
            last = i;
        } else {
            break;
        }
    }
    --a[last];
    for (int i = 0; i < n; ++i) --a[i];
    ++ans;
    while (!a.empty() && a.back() <= 0) {
        a.pop_back();
    }
    proc(a);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T --> 0) {
        int n;
        cin >> n;
        vector<int> a(n);
        ans = 0;
        for (int i = 1; i < n; ++i) {
            int x;
            cin >> x;
            ++a[--x];
        }
        a.emplace_back(1);
        sort(a.rbegin(), a.rend());
        while (!a.empty() && a.back() <= 0) a.pop_back();
        n = a.size();
        for (int i = 0; i < n; ++i) {
            a[i] = a[i] - (n - i);
            ++ans;
        }
        sort(a.rbegin(), a.rend());
        while (!a.empty() && a.back() <= 0) a.pop_back();
        proc(a);
        cout << ans << '\n';
    }
    return 0;
}

Решение 1

Будем последовательно узнавать остаток числа при делении на степени двойки. Изначально мы знаем, что остаток при делении на $$$2^0 = 1$$$ равен $$$0$$$. Как, зная остаток $$$r$$$ по модулю $$$2^k$$$, узнать загаданное число по модулю $$$2^{k+1}$$$? Для этого спросим про $$$\gcd(x + 2^k - r, 2^{k+1}) = \gcd(x+ 2^k - r, x+2^k - r+2^{k+1})$$$. Если $$$\gcd$$$ равен $$$2^{k+1}$$$, то новый остаток равен $$$r + 2^{k-1}$$$, иначе он остаётся равен $$$r$$$. Так мы дойдём до остатка загаданного числа по модулю $$$2^{30}$$$, т.е. получим само число. Получаем решение за $$$30$$$ запросов.

Решение 2

Рассмотрим множество попарно взаимно простых чисел $$${23, 19, 17, 13, 11, 9, 7, 5, 4}$$$. Их $$$\text{lcm} > 10^9$$$, поэтому если мы найдём остаток при делении $$$x$$$ на $$$\text{lcm}$$$, то мы найдём и само число $$$x$$$. Узнаем остаток числа $$$x$$$ по модулю каждого из этих чисел. Чтобы это сделать, для каждого $$$1 \le i \le 23$$$ будем спрашивать $$$\gcd(x + i, x + \text{lcm} + i)$$$, т.е запрос $$$(i, \text{lcm} + i)$$$. Если полученный $$$\gcd$$$ кратен какому-то числу из нашего множества, то остаток $$$x$$$ по модулю этого числа равен $$$-i$$$. После этого по китайской теореме об остатках мы можем восстановить $$$x$$$. Получаем решение за $$$23$$$ запроса.

Замечание 1: Достаточно сделать $$$22$$$ запроса, т.к. если для всех чисел до $$$22$$$ такого $$$i$$$ не было, то $$$23$$$ точно подойдёт.

Замечание 2: Можно не писать КТО в явном виде, это можно сделать проще, т.к. все модули маленькие, смотрите реализацию.

#include<bits/stdc++.h>

using namespace std;

int ask(int a, int b) {
    cout << '?' << " " << a << " " << a + b << endl;
    int ans;
    cin >> ans;
    return ans;
}

void solve() {
    int r = 0;
    for (int i = 1; i <= 30; i++) {
        int ans = ask((1 << (i - 1)) - r, (1 << i));
        if (ans == (1 << i)) r += (1 << (i - 1));
    }
    cout << '!' << " " << r << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
 
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#define lc 1338557220
 
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll x, rs[maxn], p;
vector<ll> pw = {23, 19, 17, 13, 11, 9, 7, 5, 4};
 
ll ask(ll a, ll b) {
    cout << "?" _ a _ b << nf;
    ll x; cin >> x; return x;
}
 
void clm(ll x) {
    cout << "!" _ x << nf;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    /* #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif */
 
    // kudos for automatic wa
 
    cin >> t;
    while (t--) {
        for (i = 1; i <= 23; i++) {
            k = ask(x + i, lc + i);
            for (j = 0; j < 9; j++) {
                if (k % pw[j] == 0) rs[j] = i % pw[j];
            }
        }
 
        k = 1; p = 1;
        for (j = 0; j < 9; j++) {
            // cout << "p =" _ p << nf;
            while (p % pw[j] != rs[j]) p += k;
            k *= pw[j];
        }
 
        clm(lc - p);
    }
 
    return 0;
}

Основная идея, на которой построено всё решение, заключается в том, что ответ обязательно находится среди не более чем 31 минимальных чисел. Тогда можно построить дерево отрезков на минимум, после чего для ответа на запрос необходимо не более чем 31 раз найти минимум (заменяя найденные минимумы на $$$\infty$$$), а потом посчитать все возможные попарные $$$OR$$$ среди этих 31 чисел.

Также можно построить Merge Sort Tree и применить те же рассуждения.

Доказательство основной идеи: докажем по индукции, что если все числа меньше $$$2^k$$$, то достаточно рассмотреть $$$k+1$$$ минимум.

База индукции: $$$k=1$$$, тогда все числа от $$$0$$$ до $$$1$$$, и утверждение очевидно.

Индуктивный переход:

Пусть для $$$k$$$ утверждение верно, докажем для $$$k+1$$$. Если у всех чисел в $$$k$$$-м бите 1, то в ответе тоже 1, поэтому нам надо минимизировать оставшиеся биты, а для них по предположению индукции достаточно рассмотреть $$$k + 1$$$ минимум. Если хотя бы у двух чисел в $$$k$$$-м бите 0, то в ответе в $$$k$$$-м бите тоже 0. Тогда нас интересуют только числа с 0 в $$$k$$$-м бите, и дальше нам нужно минимизировать оставшиеся биты, поэтому опять по предположению индукции даже $$$k+1$$$ числа хватит. Если есть ровно одно число с 0 в $$$k$$$-м бите, то в ответе $$$k$$$-й бит точно 1, и нам нужно найти $$$k+1$$$ минимальных по $$$k$$$ битам чисел. Но они точно содержатся среди $$$k+2$$$ минимальных по $$$k+1$$$ битам чисел, поэтому $$$k+2$$$ чисел хватит.

#include<bits/stdc++.h>

using namespace std;

const int MAXK = 31;
const int INF = (1 << 30);

vector<pair<int, int>> t;

pair<int, int> get(int v, int vl, int vr, int l, int r) {
    if (vl >= l && vr <= r) return t[v];
    if (r <= vl || l >= vr) return make_pair(INF, INF);
    int vm = (vl + vr) / 2;
    return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r));
}

void mod(int v, int vl, int vr, int id, int val) {
    if (vr - vl == 1) {
        t[v] = make_pair(val, id);
        return;
    }
    int vm = (vl + vr) / 2;
    if (id < vm) mod(2 * v + 1, vl, vm, id, val);
    else mod(2 * v + 2, vm, vr, id, val);
    t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &c : a) cin >> c;
    t.resize(4 * n);
    for (int i = 0; i < n; i++) mod(0, 0, n, i, a[i]);
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        vector<pair<int, int>> b;
        for (int i = 0; i < min(r - l, MAXK); i++) {
            auto now = get(0, 0, n, l, r);
            b.push_back(now);
            mod(0, 0, n, now.second, INF);
        }
        int ans = (1LL << 31) - 1;
        for (int i = 0; i < (int)b.size(); i++) {
            for (int j = i + 1; j < (int)b.size(); j++) ans = min(ans, b[i].first | b[j].first);
        }
        for (auto &c : b) mod(0, 0, n, c.second, c.first);
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}