#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
char x[N], y[N];
int main(){
int t; scanf("%d",&t);
while (t--){
scanf("%s%s", x, y);
int n = strlen(x);
long long dp[2], ndp[2];
dp[0] = (x[0]'0'?0:1) + (y[0]'0'?0:1);
dp[1] = (x[0]'1'?0:1) + (y[0]'1'?0:1);
for (int i = 1; i < n; i++){
ndp[0] = ndp[1] = (long long)1e18;
for (int p = 0; p < 2; p++){
for (int xi = 0; xi < 2; xi++){
int np = p ^ xi;
long long c = (xi != (x[i]-'0')) + (np != (y[i]-'0'));
ndp[np] = min(ndp[np], dp[p] + c);
}
}
dp[0] = ndp[0]; dp[1] = ndp[1];
}
printf("%lld\n", min(dp[0], dp[1]));
}
return 0;
}
