思路见这里

#include<bits/stdc++.h>

using namespace std ; 

const int N = 5e5 +10 ; 


int data[ N ] , data_1[ N ] ;  
int add_num[ N ] , add_num_1[ N ] ; 
int form_num[ N ][ 2 ] , form_num_1[ N ][ 2 ] ; 
int al[ N ] , al_1[ N ] ; 

int f[ N ] ; 
int n ; 


int main()
{
//	freopen("edit.in" , "r" , stdin ) ; 
//	freopen( "edit.out" , "w" , stdout ) ; 
	int T ; 
	cin >> T ;
	
	while( T -- )
	{
		cin >> n ;
		char a[ N ] , a1[ N ] , a2[ N ] , a3[ N ] ; 
		scanf("%s" , a ) ;
		scanf("%s" , a1 ) ;
		scanf("%s" , a2 ) ;
		scanf("%s" , a3 ) ;    
		for( int i = 1 ; i <= n ; i ++ )  data[ i ] = a[ i - 1 ] - '0'; 
		for( int i = 1 ; i <= n ; i ++ )  data_1[ i ] = a1[ i - 1 ] - '0' ; 
		for( int i = 1 ; i <= n ; i ++ )  al[ i ] = a2[ i - 1 ] - '0'; 
		for( int i = 1 ; i <= n ; i ++ )  al_1[ i ] = a3[ i - 1 ] - '0' ; 
		form_num[ 0 ][ 0 ] = form_num_1[ 0 ][ 0 ] = form_num[ 0 ][ 1 ] = form_num_1[ 0 ][ 1 ] = 0 ; 
		for( int i = 1 ; i <= n ; i ++ )
		{
			if( al_1[ i ] == 0 ) form_num[ i ][ 1 ] = 0 ; 
			else form_num[ i ][ 1 ] = form_num[ i - 1 ][ 1 ] + data_1[ i ] ;  
		}
		for( int i = n - 1 ; i >= 1 ; i -- )
		{
			if( al_1[ i ] == 0 ) continue ; 
			else form_num[ i ][ 1 ] = max( form_num[ i + 1 ][ 1 ] , form_num[ i ][ 1 ] ) ; 
		}
		
		for( int i = 1 ; i <= n ; i ++ )
		{
			if( al_1[ i ] == 0 ) form_num_1[ i ][ 1 ] = 0 ; 
			else form_num_1[ i ][ 1 ] = form_num_1[ i - 1 ][ 1 ] + ( data_1[ i ] + 1 ) % 2 ;  
		}
		for( int i = n - 1  ; i >= 1 ; i -- )
		{
			if( al_1[ i ] == 0 ) continue ; 
			else form_num_1[ i ][ 1 ] = max( form_num_1[ i + 1 ][ 1 ] , form_num_1[ i ][ 1 ] ) ; 
		}
		// 1 : form_num 
		for( int i = 1 ; i <= n ; i ++ )
		{
			if( al[ i ] == 0 ) form_num[ i ][ 0 ] = 0 ; 
			else form_num[ i ][ 0 ] = form_num[ i - 1 ][ 0 ] + data[ i ] ;  
		}
		for( int i = n - 1 ; i >= 1 ; i -- )
		{
			if( al[ i ] == 0 ) continue ; 
			else form_num[ i ][ 0 ] = max( form_num[ i + 1 ][ 0 ] , form_num[ i ][ 0 ] ) ; 
		}
		 // 0 : form_num_1 
		for( int i = 1 ; i <= n ; i ++ )
		{
			if( al[ i ] == 0 ) form_num_1[ i ][ 0 ] = 0 ; 
			else form_num_1[ i ][ 0 ] = form_num_1[ i - 1 ][ 0 ] + ( data[ i ] + 1 ) % 2 ;  
		}
		for( int i = n - 1 ; i >= 1 ; i -- )
		{
			if( al[ i ] == 0 ) continue ; 
			else form_num_1[ i ][ 0 ] = max( form_num_1[ i + 1 ][ 0 ] , form_num_1[ i ][ 0 ] ) ; 
		}
		
		for( int i = 1 ; i <= n ; i ++ )
			if( al[ i ] == 0 && data[ i ] == 1 ) 
			{
				if( data_1[ i ] == 0 
				&& form_num[ i + 1 ][ 1 ] - form_num[ i + 1 ][ 0 ] > 0  )
					for( int j = i ; j <= n && al_1[ j ] ; j ++ )
						if( data_1[ j ] == 1 ) 
						{
							data_1[ j ] = 0 ; 
							data_1[ i ] = 1 ; 
							break ; 
						}
				
				if( data_1[ i ] == 0 
				&& form_num[ i - 1 ][ 1 ] - form_num[ i - 1 ][ 0 ] > 0 )
					for( int j = i ; j >= 1 && al_1[ j ] ; j -- )
						if( data_1[ j ] == 1 ) 
						{
							data_1[ j ] = 0 ; 
							data_1[ i ] = 1 ; 
							break ; 
						}
			}
			else if( al[ i ] == 0 && data[ i ] == 0 ) 
			{
				if( data_1[ i ] == 1 
				&& form_num_1[ i + 1 ][ 1 ] - form_num_1[ i + 1 ][ 0 ] > 0 )
					for( int j = i ; j <= n && al_1[ j ] ; j ++ )
						if( data_1[ j ] == 0 ) 
						{
							data_1[ j ] = 1 ; 
							data_1[ i ] = 0 ; 
							break ; 
						}
				if( data_1[ i ] == 1 
				&& form_num_1[ i - 1 ][ 1 ] - form_num_1[ i - 1 ][ 0 ] > 0 ) 
					for( int j = i ; j >= 1 && al_1[ j ] ; j -- )
						if( data_1[ j ] == 0 )
						{
							data_1[ j ] = 1 ; 
							data_1[ i ] = 0 ; 
							break ; 
						}
			} 
		
		add_num[ 0 ] = add_num_1[ 0 ] = 0 ; 
		
		for( int i = 1 ; i <= n ; i ++ ) 
			add_num[ i ] = add_num[ i - 1 ] + data[ i ] ; 
		for( int i = 1 ; i <= n ; i ++ ) 
			add_num_1[ i ] = add_num_1[ i - 1 ] + data_1[ i ] ;  
		
		for( int i = n ; i >= 1 ; i -- ) add_num[ i ] = add_num[ i - 1 ] ; 
		for( int i = n ; i >= 1 ; i -- ) add_num_1[ i ] = add_num_1[ i - 1 ] ;  
		
		int fro_r = 1 ; 
		f[ 0 ] = 0 ; 
		for( int i = 1 ; i <= n ; i ++ )
		{
			if( al[ i ] == 1 )
			{
				if( add_num[ i ] - add_num[ fro_r - 1 ] > add_num_1[ i ] - add_num_1[ fro_r - 1 ] )
				{
					if( data_1[ i ] == 1 ) f[ i ] = f[ i - 1 ] + 1 ; 
					else f[ i ] = f[ i - 1 ] ; 
				}
				else if( add_num[ i ] - add_num[ fro_r - 1 ] < add_num_1[ i ] - add_num_1[ fro_r - 1 ] )
				{
					if( data[ i ] == 1 ) f[ i ] = f[ i - 1 ] + 1 ; 
					else f[ i ] = f[ i - 1 ] ; 
				}
				else 
				{
					if( data[ i ] == data_1[ i ] && data[ i ] == 1 ) f[ i ] = f[ i - 1 ] + 1 ; 
					else f[ i ] = f[ i - 1 ] ; 
				}
			}
			else 
			{
				fro_r = i + 1 ; 
				if( data[ i ] == 1 && data_1[ i ] == 1 ) f[ i ] = f[ i - 1 ] + 1 ; 
//				if( data[ i ] == data_1[ i ] ) f[ i ] = f[ i - 1 ] + 1 ; 
				else f[ i ] = f[ i - 1 ] ; 
			}
		}
		
		int all = 0 , all_0 = 0 ;
		
		for( int i = 1 ; i <= n ; i ++ ) 
			if( data[ i ] == 0 ) all_0 ++ ;
			else all ++ ;   
		for( int i = 1 ; i <= n ; i ++ )
			if( data_1[ i ] == 0 ) all_0 ++ ; 
			else all ++ ; 
		
		cout << ( all_0 - all ) / 2 + 2 * f[ n ] << endl ;  
		
	}

	return 0 ; 
}