#include<bits/stdc++.h>
using namespace std;
const char n1='\n',n2=' ';
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define de1(a) cout<<#a<<" = "<<a<<n1;
#define de2(a) cout<<#a<<" = "<<a<<n2;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define sz0(x) sz(x)-1
#define me(a,x) memset(a,x,sizeof(a))
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef map<ll,ll> mll;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef array<ll,3> a3;
typedef unsigned long long u64;
//typedef __int128 i128;
#define int long long
const int N=18;
int cost[5];
void solve(){ 
    int n;
    cin>>n;
    vector<vector<vi>> a(n+1,vector<vi>(3,vi(3)));
    rep(i,1,n){
    	rep(j,1,2){
	    	string x;
	    	cin>>x;
	    	x=' '+x;
	    	rep(k,1,2){
	    		a[i][j][k]=x[k]-'0';
	    	}
    	}
    } 
    vector<int> one(3);
    one[1]=one[2]=1;
    auto check=[&](vector<vi> &t){
    	rep(i,1,2){
            rep(j,1,2){
        		if(t[i][j]!=one[j]){
        			return false;
        		}
            }
    	}
    	return true;
    };
    set<vector<vi>> S;
    rep(i,1,n){
    	// if(check(a[i])){
    	// }
    	// else{
    		S.insert(a[i]);
    	// }
    }
    map<set<vector<vi>>,int> vis;
    multiset<pair<ll,set<vector<vi>>>> q;
    q.insert({0,S});
    while(sz(q)){
    	auto [d,cur]=*q.begin();
    	if(sz(cur)==0){
            // if(d==0)d=2;
    		cout<<d<<n1;
    		return;
    	}
    	q.erase(q.begin());
    	if(vis[cur])continue;
    	vis[cur]=1;
    	rep(i,1,2){
    		rep(j,1,2){
    			set<vector<vi>> nxt;
    			ll nd=d+cost[1];
    			for(auto b:cur){
    				b[i][j]^=1;
    				if(check(b)){
    				}
    				else{
						nxt.insert(b);    					
    				}
    			}
    			if(vis[nxt])continue;
    			q.insert({nd,nxt});
    		}
    	}
    	rep(i,1,2){
    			set<vector<vi>> nxt;
    			ll nd=d+cost[2];
    			for(auto b:cur){
    				rep(j,1,2){
    					b[i][j]^=1;
    				}
    				if(check(b)){
    				}
    				else{
						nxt.insert(b);    					
    				}
    			}
    			if(vis[nxt])continue;
    			q.insert({nd,nxt});
    	}
    	rep(j,1,2){
    			set<vector<vi>> nxt;
    			ll nd=d+cost[3];
    			for(auto b:cur){
    				rep(i,1,2){
    					b[i][j]^=1;
    				}
    				if(check(b)){
    				}
    				else{
						nxt.insert(b);    					
    				}
    			}
    			if(vis[nxt])continue;
    			q.insert({nd,nxt});
    	}

    	{
    			set<vector<vi>> nxt;
    			ll nd=d+cost[4];
    			for(auto b:cur){
    				rep(i,1,2){
    					rep(j,1,2){
    						b[i][j]^=1;
    					}
    				}
    				if(check(b)){
    				}
    				else{
						nxt.insert(b);    					
    				}
    			}
    			if(vis[nxt])continue;
    			q.insert({nd,nxt});
    	}
    }
}   
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int T=1;
    cin>>T;
    rep(i,1,4)cin>>cost[i];
    while(T--)solve();
    return 0;
}