当时 sdcpc 之前和同学 vp 了这场，大战这个题 1h+ 未果，最后破防跑路去吃饭了。
Solution
我们不妨先考虑没有 $2$ 的情况。首先有一个 trick：将所有偶数位置取反，把 $0$ 变成 $1$，把 $1$ 变成 $0$。这样删除两个相邻的 $0$ 或 $1$ 就变成了删除一个 $01$ 或 $10$ 子串。
我们惊奇地发现，由于只要有相邻不同的元素就能删除，所以这样操作后，最后剩下的一定只有 $0$ 或 $1$。所以，设 $0,\space1$ 的个数分别是 $c_0, \space c_1$，那么最后的答案一定是 $|c_0 - c_1|$。
所以我们发现，答案与 $0$ 和 $1$ 的位置无关，只和个数有关。那么考虑 $2$ 就很简单了，直接枚举有几个变成 $0$，几个变成 $1$，然后对所有情况取 $\max$ 即可。
Code
// Problem: P14015 [ICPC 2024 Nanjing R] 生日礼物
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14015
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define ls x << 1
#define rs x << 1 | 1
using namespace std;
// const int maxn = ;
void solve(){
string s ; cin >> s ;
int n = s.size() ;
s = 'a' + s ;
for(int i = 2; i <= n; i += 2) {
if(s[i] != '2') s[i] = (s[i] == '0' ? '1' : '0') ;
}
int cnt[3] = {0, 0, 0} ;
rep(i, 1, n) {
cnt[s[i] - '0'] ++ ;
}
int ans = 2e9 ;
rep(c0, 0, cnt[2]) {
ans = min(ans, abs(c0 + cnt[0] - cnt[1] - (cnt[2] - c0))) ;
}
cout << ans << endl ;
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1 ;
cin >> T ;
while(T -- ){
solve() ;
}
return 0 ;