#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e4+10,inf=1e9+10;
int f[N][2][3],T,n,ans;//0被0覆盖1被1覆盖int ans=1<<62; 
char a[N],b[N];
int main(){
	cin>>T;
	while(T--){
		cin>>b>>a;
		ans=inf;
		n=0;
		while(a[n]!=0){
			n++;
		}
		memset(f,62,sizeof(f));
		if(a[0]==b[0]){
			f[0][0][2]=0;
			if(a[0]=='0')
			f[0][1][1]=2;
			else
			f[0][1][0]=2;
		}
		else
		{
		f[0][1][0]=1;
			if(a[0]='0')
			{
				f[0][1][1]=2;
				f[0][0][0]=1;
			}
			else{
				f[0][1][0]=2;
				f[0][0][1]=1;
			}
		}
		for(int i=1;i<n;i++){
			if(a[i]==b[i]){
			for(int j=0;j<2;j++)
						for(int k=0;k<3;k++)
						f[i][0][2]=min(f[i-1][j][k],f[i][0][2]);
				if(a[i]=='1'){
						f[i][1][0]=min(f[i][1][0],f[i-1][0][0]+1);
						f[i][1][0]=min(f[i][1][0],f[i-1][0][1]+2);
						f[i][1][0]=min(f[i][1][0],f[i-1][0][2]+2);
						f[i][1][0]=min(f[i][1][0],f[i-1][1][0]);
						f[i][1][0]=min(f[i][1][0],f[i-1][1][1]+1);
						f[i][1][0]=min(f[i][1][0],f[i-1][1][2]+1);
				}
				if(a[i]=='0'){
					f[i][1][1]=min(f[i][1][1],f[i-1][0][0]+2);
						f[i][1][1]=min(f[i][1][1],f[i-1][0][1]+1);
						f[i][1][1]=min(f[i][1][1],f[i-1][0][2]+2);
						f[i][1][1]=min(f[i][1][1],f[i-1][1][0]+1);
						f[i][1][1]=min(f[i][1][1],f[i-1][1][1]);
						f[i][1][1]=min(f[i][1][1],f[i-1][1][2]+1);
				}
			}
			else{
				if(a[i]=='1'){
					f[i][1][2]=min(f[i][1][2],f[i-1][0][0]+1);
						f[i][1][2]=min(f[i][1][2],f[i-1][0][1]+1);
						f[i][1][2]=min(f[i][1][2],f[i-1][0][2]+1);
						f[i][1][2]=min(f[i][1][2],f[i-1][1][0]);
						f[i][1][2]=min(f[i][1][2],f[i-1][1][1]);
						f[i][1][2]=min(f[i][1][2],f[i-1][1][2]);
						
						f[i][1][0]=min(f[i][1][0],f[i-1][0][0]+1);
						f[i][1][0]=min(f[i][1][0],f[i-1][0][1]+2);
						f[i][1][0]=min(f[i][1][0],f[i-1][0][2]+2);
						f[i][1][0]=min(f[i][1][0],f[i-1][1][0]);
						f[i][1][0]=min(f[i][1][0],f[i-1][1][1]+1);
						f[i][1][0]=min(f[i][1][0],f[i-1][1][2]+1);
						
						f[i][0][1]=min(f[i][0][1],f[i-1][0][0]+1);
						f[i][0][1]=min(f[i][0][1],f[i-1][0][1]);
						f[i][0][1]=min(f[i][0][1],f[i-1][0][2]+1);
						f[i][0][1]=min(f[i][0][1],f[i-1][1][0]+1);
						f[i][0][1]=min(f[i][0][1],f[i-1][1][1]);
						f[i][0][1]=min(f[i][0][1],f[i-1][1][2]+1);
				}
				if(a[i]=='0'){
					f[i][1][2]=min(f[i][1][2],f[i-1][0][0]+1);
						f[i][1][2]=min(f[i][1][2],f[i-1][0][1]+1);
						f[i][1][2]=min(f[i][1][2],f[i-1][0][2]+1);
						f[i][1][2]=min(f[i][1][2],f[i-1][1][0]);
						f[i][1][2]=min(f[i][1][2],f[i-1][1][1]);
						f[i][1][2]=min(f[i][1][2],f[i-1][1][2]);
						
						f[i][1][1]=min(f[i][1][1],f[i-1][0][0]+2);
						f[i][1][1]=min(f[i][1][1],f[i-1][0][1]+1);
						f[i][1][1]=min(f[i][1][1],f[i-1][0][2]+2);
						f[i][1][1]=min(f[i][1][1],f[i-1][1][0]+1);
						f[i][1][1]=min(f[i][1][1],f[i-1][1][1]);
						f[i][1][1]=min(f[i][1][1],f[i-1][1][2]+1);
						
						f[i][0][0]=min(f[i][0][0],f[i-1][0][0]);
						f[i][0][0]=min(f[i][0][0],f[i-1][0][1]+1);
						f[i][0][0]=min(f[i][0][0],f[i-1][0][2]+1);
						f[i][0][0]=min(f[i][0][0],f[i-1][1][0]);
						f[i][0][0]=min(f[i][0][0],f[i-1][1][1]+1);
						f[i][0][0]=min(f[i][0][0],f[i-1][1][2]+1);
				}
			}
		}
		for(int i=0;i<2;i++){
			for(int j=0;j<3;j++)
			ans=min(ans,f[n-1][i][j]);
		} 
		cout<<ans<<endl;
	}
}