#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull long long
#define PII pair<int ,int>
const int INF = 0x3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
int fp(int a, int x, int mod) {
int ans = 1;
while (x) {
if (x & 1)ans *= a;
ans %= mod;
a *= a;
a %= mod;
x >>= 1;
}
return ans;
}
int a[N], nxt[N], last[N];
int aa[N], nxxt[N], laast[N],top=0;
int stt[3][N], topp[3] = { 0.0,0 };
void solve() {
string s;
cin >> s;
int st = 0;
int len = s.length();
for (int i = 0; i < s.length(); i++) {
a[i] = s[i] - '0';
nxt[i] = i + 1;
last[i] = i - 1;
}
top = 0;
for (int i = 0; i < 3; i++)topp[i] = 0;
for (int i = len; i <= len+5; i++) {
a[i] = 3;
nxt[i] = len + 1;
last[i] = len + 1;
}
for (int i = 0; i < len; i=nxt[i]) {
if (a[i] == a[nxt[i]] && a[i] != 2) {
int t = i;
if (i == st) {
st = nxt[nxt[i]];
i = last[st];
}
else {
nxt[last[i]] = nxt[nxt[i]];
last[nxt[nxt[i]]] = last[i];
i = last[last[i]];
}
a[t] = 3;
}
}
for (int i = st; i < len; i=nxt[i]) {
// cout << a[i];//test
aa[top] = a[i];
top++;
}
// cout << endl;//test
vector<int> k01, k02, k11, k12;
int cnt2 = 0;
for (int i = 0; i < top; i++) {
if (i % 2 == 1) {
if (aa[i] == 0)k01.push_back(i);
else if(aa[i]==1)k11.push_back(i);
}
else {
if (aa[i] == 0)k02.push_back(i);
else if (aa[i] == 1)k12.push_back(i);
}
}
int ans = top;
if (k01.size() && k02.size()) {
int i = k01[0], j = k02[k02.size() - 1];
cnt2 = 0;
if (j > i) {
for (int ii = 0; ii < i; ii++) {
if (aa[ii] == 2)cnt2++;
}
for (int ii = j; ii < top; ii++) {
if (aa[ii] == 2)cnt2++;
}
ans = min(ans, top - cnt2 - (j - i + 1));
}
i = k02[0], j = k01[k01.size() - 1];
cnt2 = 0;
if (j > i) {
for (int ii = 0; ii < i; ii++) {
if (aa[ii] == 2)cnt2++;
}
for (int ii = j; ii < top; ii++) {
if (aa[ii] == 2)cnt2++;
}
ans = min(ans, top - cnt2 - (j - i + 1));
}
}
if (k11.size() && k12.size()) {
int i = k11[0], j = k12[k12.size() - 1];
cnt2 = 0;
if (j > i) {
for (int ii = 0; ii < i; ii++) {
if (aa[ii] == 2)cnt2++;
}
for (int ii = j; ii < top; ii++) {
if (aa[ii] == 2)cnt2++;
}
ans = min(ans, top - 2*cnt2 - (j - i + 1));
}
i = k12[0], j = k11[k11.size() - 1];
cnt2 = 0;
if (j > i) {
for (int ii = 0; ii < i; ii++) {
if (aa[ii] == 2)cnt2++;
}
for (int ii = j; ii < top; ii++) {
if (aa[ii] == 2)cnt2++;
}
ans = min(ans, top - 2*cnt2 - (j - i + 1));
}
}
for (int i = 0; i < top; i++) {
if(aa[i]==2)cnt2++;
}
ans = min(ans, top - 2 * cnt2);
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
/*
2
01020102
01202010
*/
/*
f (aa[i] == 1) {
st1[top1++] = i;
if (top1 >= 2) {
if (top2 < 1 && top0 < 1) {
top1 -= 2;
}
else if (top2 < 1 && st0[top0 - 1] < st1[top1 - 2]) {
top1 -= 2;
}
else if (top0 < 1 && st2[top2 - 1] < st1[top1 - 2]) {
top1 -= 2;
}
else if (top2 >= 1 && top1 >= 1) {
if (st0[top0 - 1] < st1[top1 - 2] && st2[top2 - 1] < st1[top1 - 2]) {
top1 -= 2;
}
else {
int las = st1[top1 - 2];
if ((las - i+1) % 2 == 0) {
int k2 = st2[top2 - 1], k0 = st0[top0 - 1];
while ((k0 > las || k2 > las)) {
if (abs(k2 - k0) == 1) {
top2--;
top0--;
}
else break;
k2 = st2[top2 - 1], k0 = st0[top0 - 1];
}
if (top2 < 1 && top0 < 1) {
top1 -= 2;
}
else if (top2 < 1 && st0[top0 - 1] < st1[top1 - 2]) {
top1 -= 2;
}
else if (top0 < 1 && st2[top2 - 1] < st1[top1 - 2]) {
top1 -= 2;
}
else if (top2 >= 1 && top1 >= 1) {
if (st0[top0 - 1] < st1[top1 - 2] && st2[top2 - 1] < st1[top1 - 2]) {
top1 -= 2;
}
}
}
}
}
}
}
else if (aa[i] == 0) {
st0[top0++] = i;
if (top0 >= 2) {
if (top2 < 1 && top1 < 1) {
top0 -= 2;
}
else if (top2 < 1 && st1[top1 - 1] < st0[top0 - 2]) {
top0 -= 2;
}
else if (top1 < 1 && st2[top2 - 1] < st0[top0 - 2]) {
top0 -= 2;
}
else if (top2 >= 1 && top1 >= 1) {
if (st1[top1 - 1] < st0[top0 - 2] && st1[top1 - 1] < st0[top0 - 2]) {
top0 -= 2;
}
else {
int las = st0[top0 - 2];
if ((las - i+1) % 2 == 0) {
int k2 = st2[top2 - 1], k1 = st1[top1 - 1];
while (k1 > las || k2 > las) {
if (abs(k2 - k1) == 1) {
top2--;
top1--;
}
else {
break;
}
k2 = st2[top2 - 1], k1 = st0[top1 - 1];
}
if (top2 < 1 && top1 < 1) {
top0 -= 2;
}
else if (top2 < 1 && st1[top1 - 1] < st0[top0 - 2]) {
top0 -= 2;
}
else if (top1 < 1 && st2[top2 - 1] < st0[top0 - 2]) {
top0 -= 2;
}
else if (top2 >= 1 && top1 >= 1) {
if (st1[top1 - 1] < st0[top0 - 2] && st1[top1 - 1] < st0[top0 - 2]) {
top0 -= 2;
}
}
}
}
}
}
}
else if (aa[i] == 2) {
st2[top2++] = i;
}
}
while (st1[top1 - 1] - st1[top1 - 2] == 1&&top1>=2) {
top1 -= 2;
}
while (st0[top0 - 1] - st0[top0 - 2] == 1&&top0>=2) {
top0 -= 2;
}
*/