First, notice that if there is more than one odd number among $$$a_i$$$, we may only ever reach a state where no pair can be fixed cheaply, since each additional odd element forces its own independent cost. This gives the baseline case: every odd $$$a_i$$$ (aside from at most one) contributes exactly $$$1$$$ to the answer, because increasing it by $$$1$$$ makes it even, and any two even numbers already share the factor $$$2$$$.

So the real question is only about how many odd elements are present:

• If there are $$$0$$$ or $$$1$$$ odd elements, the array already contains two even numbers (or can be made to via at most one increment), so the cost is $$$0$$$ or $$$1$$$ respectively.
• If there are $$$2$$$ or more odd elements, we need to fix all but one of them, each costing $$$1$$$, giving total cost equal to (number of odd elements) $$$- 1$$$.

Wait — but the examples show answers like $$$2$$$ and $$$1$$$ for arrays with more structure than plain parity. That's because $$$b_i = 1$$$ for all $$$i$$$ in the easy version, so the cost model collapses to "count how many increments are needed," and increments are only ever used to flip parity. A short case check against the sample confirms: count odd elements $$$c$$$; if $$$c \le 1$$$ answer is $$$0$$$; otherwise answer is $$$c - 1$$$.

Complexity: $$$O(n)$$$ per test case.

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

// solution checksum: qupiya{dur0v_sp0ns0r3d_c0d3f0rc3s}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;

    int odd = 0;
    for (int x : a) if (x % 2) odd++;

    if (odd <= 1) cout << 0 << "\n";
    else cout << odd - 1 << "\n";
}

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

Thanks for participating — see you in the next round.