/*
    author: honglan0301
    sexy_goodier_xiaoqing
    tangshi_xsap

    goodier didi123 mc123456 xsap HYX1124 wuyouka JiaYou!!!!!!!!!!!!!!!!
    flying bunH2O 1437vszombies... Jiayou!!!!!!!!!

    last dance~
*/
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
mt19937_64 rndl(time(0));
#define int long long
#define ll long long
#define ull unsigned long long
#define mod 998244353
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"

int T,n,ans;
char s1[100005],s2[100005],t1[100005],t2[100005];
int top1,top2;
pair<pair<int,int>,pair<int,int>> stk1[100005],stk2[100005];

pair<pair<int,int>,pair<int,int>> solve(pair<pair<int,int>,pair<int,int>> nl,pair<pair<int,int>,pair<int,int>> nr)
{
    //cout<<nl.fi.fi<<" "<<nl.fi.se<<" "<<nr.fi.fi<<" "<<nr.fi.se<<" "<<nl.se.fi<<" "<<nl.se.se<<" "<<nr.se.fi<<" "<<nr.se.se<<endl;
    pair<pair<int,int>,pair<int,int>> nto;
    nto.fi.fi=nl.fi.se+1; nto.fi.se=nr.fi.se;
    ans+=nl.fi.se-nl.fi.fi+1;
    if(nr.se.fi>=nl.se.fi&&nr.se.se>=nl.se.se)
    {
        nto.se.fi=nr.se.fi-nl.se.fi; nto.se.se=nr.se.se-nl.se.se;
    }
    else if(nr.se.fi>=nl.se.fi)
    {
        ans-=nl.se.se-nr.se.se;
        nto.se.se=0; nto.se.fi=nto.fi.se-nto.fi.fi+1;
    }
    else
    {
        ans-=nl.se.fi-nr.se.fi;
        nto.se.fi=0; nto.se.se=nto.fi.se-nto.fi.fi+1;
    }
    return nto;
}

signed main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    cin>>T;
    while(T--)
    {
        cin>>n>>(s1+1)>>(s2+1)>>(t1+1)>>(t2+1);
        top1=top2=ans=0;
        int lst1=n+1,nr0=0,nr1=0;
        for(int i=n;i>=1;i--)
        {
            if(t1[i]=='0')
            {
                if(nr0||nr1)
                {
                    stk1[++top1]=mp(mp(i+1,lst1-1),mp(nr0,nr1));
                    nr0=nr1=0; lst1=i+1;
                }
                nr0+=s1[i]=='0',nr1+=s1[i]=='1';
                stk1[++top1]=mp(mp(i,lst1-1),mp(nr0,nr1));
                nr0=nr1=0; lst1=i;
                continue;
            }
            nr0+=s1[i]=='0',nr1+=s1[i]=='1';
        }
        if(nr0||nr1)
        {
            stk1[++top1]=mp(mp(1,lst1-1),mp(nr0,nr1));
            nr0=nr1=0;
        }
        int lst2=n+1; nr0=0; nr1=0;
        for(int i=n;i>=1;i--)
        {
            if(t2[i]=='0')
            {
                if(nr0||nr1)
                {
                    stk2[++top2]=mp(mp(i+1,lst2-1),mp(nr0,nr1));
                    nr0=nr1=0; lst2=i+1;
                }
                nr0+=s2[i]=='0',nr1+=s2[i]=='1';
                stk2[++top2]=mp(mp(i,lst2-1),mp(nr0,nr1));
                nr0=nr1=0; lst2=i;
                continue;
            }
            nr0+=s2[i]=='0',nr1+=s2[i]=='1';
        }
        if(nr0||nr1)
        {
            stk2[++top2]=mp(mp(1,lst2-1),mp(nr0,nr1));
            nr0=nr1=0;
        }
        while(top1&&top2)
        {
            pair<pair<int,int>,pair<int,int>> nl=stk1[top1--],nr=stk2[top2--],na;
            if(nl.fi.se<=nr.fi.se)
            {
                na=solve(nl,nr);
                if(na.se.fi||na.se.se) stk2[++top2]=na;
            }
            else
            {
                na=solve(nr,nl);
                if(na.se.fi||na.se.se) stk1[++top1]=na;
            }
        }
        cout<<ans<<endl;
    }
}
/*
9
101111111
100111000
110111011
011111111

*/