~~~~~

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 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 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 color(n, -1); deque 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> 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> sl; vector 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(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 v; for (int sum = sum0, ad = 0, pref = 0; sum < n + m; sum += 2, ad++) { vector 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';
}

}~~~~~