//
// Created by 19233 on 2024/11/25.
//
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <memory>
#include <bitset>

using namespace std;

using lllp = pair<pair<long long,long long>,long long>;

long long a[4];

struct PairHash {
    std::size_t operator()(const std::pair<long long, long long>& p) const {
      return std::hash<long long>()(p.first) ^ (std::hash<long long>()(p.second) << 1);
    }
};

struct PairEqual {
    bool operator()(const std::pair<long long, long long>& p1, const std::pair<long long, long long>& p2) const {
      return p1.first == p2.first && p1.second == p2.second;
    }
};

unordered_map<pair<long long,long long>,long long,PairHash,PairEqual>vis;

void light(pair<long long int, long long int> &state , int m)
{
  for(int i=0;i<m;++i)
  {
    int j=0;
    for(;j<4;++j)
    {
      if(!((state.first>>(j+i*4))&1))
        break;
    }
    if(j==4)
    {
      state.second|=(1<<i);
    }
  }
}

vector<lllp> single (const pair<long long int,long long> state, long long cost, int m)
{
  vector<lllp>res;
  long long pay = cost+a[0];
  pair<long long int,long long> check ;
  for(int i=0;i<4;++i)
  {
    check=state;
    for(int j=0;j<m;++j)
    {
      check.first^=(1<<(i+j*4));
    }
    light(check,m);
    if(vis.find(check)==vis.end())
      res.emplace_back(check,pay);
  }
  return res;
}

vector<lllp> row (const pair<long long int, long long int> state, long long cost, int m)
{
  vector<lllp>res;
  long long pay = cost+a[1];
  pair<long long int,long long> check ;
  for(int i=0;i<4;i+=2)
  {
    check=state;
    for(int j=0;j<m;++j)
    {
      check.first^=(1<<(j*4+i));
      check.first^=(1<<(j*4+i+1));
    }
    light(check,m);
    if(vis.find(check)==vis.end())
      res.emplace_back(check,pay);
  }
  return res;
}

vector<lllp> col (const pair<long long int, long long int> state, long long cost, int m)
{
  vector<lllp>res;
  long long pay = cost+a[2];
  pair<long long,long long> check;
  for(int i=0;i<2;++i)
  {
    check=state;
    for (int j = 0; j < m; ++j)
    {
      check.first^=(1<<(j*4+i));
      check.first^=(1<<(j*4+i+2));
    }
    light(check,m);
    if(vis.find(check)==vis.end())
      res.emplace_back(check,pay);
  }
    return res;
}

vector<lllp> all (pair<long long int, long long int> state, long long cost, int m)
{
  vector<lllp>res;
  long long pay = a[3]+cost;
  for(int i=0;i<m*4;++i)
    state.first^= (1<<(i));
  light(state,m);
  if(vis.find(state)==vis.end())
    res.emplace_back(state,pay);
  return res;
}

void solve()
{
  int m;
  cin>>m;
  char c;
  pair<long long,long long> state;
  long long end=(1<<m)-1;
  state.first=state.second=0;
  for(int i=0;i<m*4;++i)
  {
    cin>>c;
    state.first|=((c-'0')<<i);
  }

  auto cmp = [](const lllp&a, const lllp&b){
      return a.second>b.second;
  };
  priority_queue<lllp,vector<lllp>, decltype(cmp)>dui(cmp);
  for(auto &i: single(state,0,m))
    dui.emplace(i);
  for(auto &i: col(state,0,m))
    dui.emplace(i);
  for(auto &i:row(state,0,m))
    dui.emplace(i);
  for(auto &i:all(state,0,m))
    dui.emplace(i);

  while (!dui.empty())
  {
    auto [now,cost] = dui.top();
    dui.pop();
    if(vis.find(now)!=vis.end())
      continue;
    else
      vis.insert({now,cost});
    if(now.second==end)
    {
      cout<<cost<<'\n';
      return;
    }
    for(auto &i: single(now,cost,m))
      dui.emplace(i);
    for(auto &i: col(now,cost,m))
      dui.emplace(i);
    for(auto &i:row(now,cost,m))
      dui.emplace(i);
    for(auto &i:all(now,cost,m))
      dui.emplace(i);
  }
}

int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
  int T=1;
  cin>>T;
  for(long long & i : a)
    cin>>i;
  while (T--)
  {
    solve();
    vis.clear();
  }
}