#include <bits/stdc++.h>
using namespace std;
int t,n,dp[500010][4][4];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);
	for (int i=0;i<4;i++) for (int j=0;j<4;j++) dp[0][i][j]=(i>0)+(j>0);
	cin>>t;
	while (t--){
		string s1,s2;cin>>s2>>s1;
		int n=s1.size();
		for (int i=1;i<=n;++i){
			for (int j=0;j<4;++j){
				for (int k=0;k<4;++k){
					dp[i][j][k]=1e9;
					for (int f=0;f<4;++f)
						for (int g=0;g<4;++g)
							dp[i][j][k]=min(dp[i][j][k],dp[i-1][f][g]+(j&&j^f)+(k&&k^g));	
				}
			}
			if (s1[i-1]==s2[i-1]){
				if (s1[i-1]=='1') dp[i][3][0]=dp[i][0][3]=dp[i][1][1]=dp[i][0][1]=dp[i][2][1]=dp[i][3][1]=dp[i][1][0]=dp[i][2][3]=1e9;
				else dp[i][2][0]=dp[i][3][0]=dp[i][0][2]=dp[i][1][2]=dp[i][2][2]=dp[i][3][2]=dp[i][0][3]=dp[i][1][3]=1e9;
			}
			else{
				if (s1[i-1]=='1') dp[i][0][0]=dp[i][1][0]=dp[i][0][1]=dp[i][1][1]=dp[i][2][1]=dp[i][3][1]=dp[i][2][3]=dp[i][3][3]=1e9;
				else dp[i][0][0]=dp[i][2][0]=dp[i][0][2]=dp[i][1][2]=dp[i][2][2]=dp[i][3][2]=dp[i][1][3]=dp[i][3][3]=1e9;
			}
		}
		int ans=1e9;
		for (int j=0;j<4;j++) for (int k=0;k<4;k++) if (dp[n][j][k]<ans)ans=dp[n][j][k];
		cout<<ans<<'\n';
	}
    return 0;
}