using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 1e5 + 11;
int n, sz[NMAX];
vi g[NMAX];
void calc_sz(int u, int p)
{
    sz[u] = 1;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        calc_sz(v, u);
        sz[u] += sz[v];
    }
}
int find_centroid(int u, int p, int n)
{
    for (auto v : g[u])
        if (v != p and sz[v] > n / 2)
            return find_centroid(v, u, n);
    return u;
}
ii find_leaf(int u, int p)
{
    int vmax = 0;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        if (sz[v] > sz[vmax])
            vmax = v;
    }
    if (vmax == 0)
        return {p, u};
    return find_leaf(vmax, u);
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(sz, 0, sizeof sz);
        for (int i = 0; i < NMAX; ++i)
            g[i].clear();
        cin >> 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);
        }
        int root = 1;
        calc_sz(root, -1);
        root = find_centroid(root, -1, n);
        memset(sz, 0, sizeof sz);
        calc_sz(root, -1);
        auto [u, v] = find_leaf(root, -1);
        cout << u << " " << v << endl;
        cout << root << " " << v << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        set<int> once, more;
        for (int i = 0; i < n; ++i)
        {
            int ai;
            cin >> ai;
            if (once.find(ai) == once.end())
                once.insert(ai);
            else
                more.insert(ai);
        }
        int x = 0;
        while (more.find(x) != more.end())
            ++x;
        int y = x;
        while (once.find(y) != once.end())
            ++y;
        cout << x + y << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
bool solve(string s, int k)
{
    int n = (int)s.size();;
    string t(s.begin(), s.begin() + k);
    for (int i = k; i < n; i += k)
    {
        for (int j = 0; j < k and j + i < n; ++j)
        {
            int ix = i + j;
            if (s[ix] != '?' and t[j] == '?')
                t[j] = s[ix];
            else if (s[ix] != '?' and t[j] != '?' and s[ix] != t[j])
                return false;
        }
    }
    int zeros = count_if(t.begin(), t.end(), [](char c) { return c == '0'; });
    int ones = count_if(t.begin(), t.end(), [](char c) { return c == '1'; });
    return ones <= k / 2 and zeros <= k / 2;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        string s;
        cin >> n >> k;
        cin >> s;
        cout << (solve(s, k) ? "YES" : "NO") << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vll = vector<ll>;
ll solve(vll &a)
{
    int n = (int)a.size();;
    ll ans = 0;
    int l = 0, r = n - 1;
    for (int i = n - 1; i >= 0; --i)
    {
        if (a[i] > 0)
        {
            while (r > i and a[i] > 0)
            {
                if (a[r] < 0)
                {
                    auto diff = min(a[i], abs(a[r]));
                    a[i] -= diff;
                    a[r] += diff;
                }
                if (a[r] == 0)
                    --r;
            }
            while (l < i and a[i] > 0)
            {
                if (a[l] < 0)
                {
                    auto diff = min(a[i], abs(a[l]));
                    a[i] -= diff;
                    a[l] += diff;
                    ans += diff;
                }
                if (a[l] >= 0)
                    ++l;
            }
        }
    }
    return ans;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vll a(n);
        for (auto &ai : a)
            cin >> ai;
        cout << solve(a) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi a(n);
        for (auto &ai : a)
            cin >> ai;
        reverse(a.begin(), a.end());
        for (auto ai : a)
            cout << ai << " ";
        cout << endl;
    }
    return 0;
}

using namespace std;
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
int main(void)
{
    int t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        vector<bool> ok(n, false);
        vector<int> sorted, ans(n), a(n);
        for (auto &ai : a)
            cin >> ai;
        int minv = *min_element(a.begin(), a.end());
        for (int i = 0; i < n; ++i)
        {
            if (gcd(a[i], minv) == minv)
            {
                ok[i] = true;
                sorted.push_back(a[i]);
            }
        }
        int j = 0;
        sort(sorted.begin(), sorted.end());
        for (int i = 0; i < n; ++i)
        {
            if (ok[i])
                ans[i] = sorted[j++];
            else
                ans[i] = a[i];
        }
        cout << (is_sorted(ans.begin(), ans.end()) ? "YES" : "NO") << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ds = array<array<ll, 3>, 2>;
ll solve(ds s012)
{
    ll ans = 0;
    ll temp = min(s012[0][2], s012[1][1]);
    ans += 2 * temp;
    s012[0][2] -= temp;
    s012[1][1] -= temp;
    if (s012[0][2] > 0)
    {
        temp = min(s012[0][2], s012[1][2]);
        s012[0][2] -= temp;
        s012[1][2] -= temp;
    }
    if (s012[0][2] > 0)
    {
        temp = min(s012[0][2], s012[1][0]);
        s012[0][2] -= temp;
        s012[1][0] -= temp;
    }
    if (s012[1][2] > 0)
    {
        temp = min(s012[1][2], s012[0][0]);
        s012[1][2] -= temp;
        s012[0][0] -= temp;
    }
    if (s012[1][2] > 0)
    {
        temp = min(s012[1][2], s012[0][1]);
        ans -= 2 * temp;
        s012[1][2] -= temp;
        s012[0][1] -= temp;
    }
    return ans;
}
ll solve2(ds s012)
{
    ll a1 = min(s012[0][2], s012[1][1]);
    ll b0 = s012[1][0] + s012[1][1] - a1;
    ll b1 = max(min(s012[0][1] - b0, s012[1][2]), 0LL);
    return 2 * a1 - 2 * b1;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        ds xyz;
        for (int s = 0; s < 2; ++s)
            for (int i = 0; i < 3; ++i)
                cin >> xyz[s][i];
        cout << solve2(xyz) << endl;
    }
    return 0;
}

using namespace std;
int solve(int n, int k)
{
    if (n < k)
        return k - n;
    else
        return n % 2 != k % 2;
}
int main(void)
{
    int t, n, k;
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
int main(void)
{
    int t, n;
    string s;
    vi ans;
    set<ii> frontier;
    cin >> t;
    while (t--)
    {
        cin >> n >> s;
        ans.assign(n, -1);
        for (int i = 0; i < n; ++i)
        {
            auto it = frontier.lower_bound({'1' - s[i], 0});
            if (it != frontier.end() and it->first != (s[i] - '0'))
            {
                auto [t, id] = *it;
                frontier.erase(it);
                ans[i] = id;
                frontier.insert({s[i] - '0', ans[i]});
            }
            else
            {
                ans[i] = frontier.size();
                frontier.insert({s[i] - '0', ans[i]});
            }
        }
        cout << frontier.size() << endl;
        for (int i = 0; i < n; ++i)
            cout << ans[i] + 1 << " ";
        cout << endl;
        frontier.clear();
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
int const NMAX = 55;
int solve(int n, vi w)
{
    map<int, int> sum_count;
    vi freq(NMAX, 0);
    for (int i = 0; i < n; ++i)
        freq[w[i]]++;
    for (int i = 1; i < NMAX; ++i)
    {
        for (int j = i; j < NMAX; ++j)
        {
            if (i == j)
                sum_count[i + j] += freq[i] / 2;
            else
                sum_count[i + j] += min(freq[i], freq[j]);
        }
    }
    return max_element(sum_count.begin(),
                       sum_count.end(),
                       [](const auto &p1, const auto &p2) {
                           return p1.second < p2.second;
                       })
        ->second;
}
int main(void)
{
    int t, n;
    vi w;
    cin >> t;
    while (t--)
    {
        cin >> n;
        w.resize(n);
        for (auto &wi : w)
            cin >> wi;
        cout << solve(n, w) << endl;
    }
    return 0;
}