#include<bits/stdc++.h>
using namespace std;
constexpr int mxn{1000005};
int T,dp[mxn][3];
int get(bitset<mxn>const&S,bitset<mxn>const&T)
{
	int res=0;
	for(int i=0;i<mxn;++i)
		if(S[i]^T[i])
			res=i+1;
	return res;
}
int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		bitset<mxn>S,T;
		cin>>S>>T;
		int const n=get(S,T);
		dp[0][T[0]]=1;
		dp[0][!T[0]]=2;
		dp[0][2]=S[0]^T[0];
		for(int i=1;i<n;++i)
		{
			dp[i][T[i]]=min({dp[i-1][T[i-1]]+T[i]^T[i-1],dp[i-1][!T[i-1]]+T[i]^!T[i-1],dp[i-1][2]+1});//no xor
			dp[i][!T[i]]=min({dp[i-1][T[i-1]]+1+T[i-1]^!T[i],dp[i-1][!T[i-1]]+T[i]^T[i-1],dp[i-1][2]+1+(S[i-1]==T[i-1])});//yes xor
			if(S[i]^T[i])
				dp[i][2]=min({dp[i-1][T[i-1]]+1,dp[i-1][!T[i-1]],dp[i-1][2]+(S[i-1]==T[i-1])});
			else
				dp[i][2]=min({dp[i-1][T[i-1]],dp[i-1][!T[i-1]],dp[i-1][2]});
		}
		cout<<min({dp[n-1][0],dp[n-1][1],dp[n-1][2]})<<'\n';
	}
	return 0;
}