#include <bits/stdc++.h>
#define b4 bitset<4>
//#define int long long
using namespace std;
const int mod = 998244353;
const int N = 1e5 + 7;
int d[16][16];
b4 bs[16];
struct node{
    b4 s;
    int cost;
};
struct cmp{
    bool operator () (node a,node b){
        return (a.cost>b.cost);
    }
};
int vs(b4 &s){return 1*s[0]+2*s[1]+4*s[2]+8*s[3];}
void solve() {
    int m;
    cin>>m;
    vector<int>a(m);
    for(int i=0;i<m;i++){
        string q,w;cin>>q>>w;
        q+=w;
        bitset<4>s(q);
        a[i]=vs(s);
    }
    int ans=INT_MAX;
    set<int>hh;
    for(int i=0;i<m;i++)hh.insert(i);
    for(int i=0;i<m;i++){
        set<int>h=hh;
        int cost=0,cur=i;
        cost+=d[a[cur]][15];
        h.erase(cur);
        while(!h.empty()){
            int to=*h.begin(),ct=d[a[cur]][a[to]];
            for(int s:h)if(d[a[cur]][a[s]]<ct){to=s;ct=d[a[cur]][a[to]];}
            cost+=ct;
            cur=to;
            h.erase(to);
        }
        ans=min(ans,cost);
    }
    if(ans==0)ans=2;
    cout<<ans<<"\n";
}
/*
 2 1000 100 10 1
 4
 10
 00
 01
 00
 00
 10
 00
 01
 1
 11
 11
 * */
signed main() {
    for(auto & i : d)
        for(auto & j : i)
            j=-1;
    for(int i=0;i<16;++i){
        bitset<4> s("0000");
        int id=i;
        for(int j=0;j<4;++j){
            if(id&1)s[j]=1;
            id>>=1;
        }
        bs[i]=s;
    }

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    cin >> t;
    int a0,a1,a2,a3;cin>>a0>>a1>>a2>>a3;
    for(int i=0;i<16;++i){
        priority_queue<node,vector<node>,cmp>q;
        q.push({bs[i],0});
        while(!q.empty()){
            b4 s=q.top().s;
            int cost=q.top().cost;
            int id=vs(s);
            q.pop();
            if(d[i][id]!=-1)continue;
            d[i][id]=cost;
            b4 r;
            for(int j=0;j<4;++j){r=s;r[j]=!r[j];q.push({r,cost+a0});}
            r=s;r[0]=!r[0];r[1]=!r[1];q.push({r,cost+a1});
            r=s;r[2]=!r[2];r[3]=!r[3];q.push({r,cost+a1});
            r=s;r[0]=!r[0];r[2]=!r[2];q.push({r,cost+a2});
            r=s;r[1]=!r[1];r[3]=!r[3];q.push({r,cost+a2});
            r=s;r[0]=!r[0];r[1]=!r[1];r[2]=!r[2];r[3]=!r[3];q.push({r,cost+a3});
        }
    }
    for (int i = 0; i < t; ++i) {
        solve();
    }

    return 0;
}