#include <bits/stdc++.h>

 using namespace std;

 const int maxn =  *  + ;

 const int INF = ;

 struct Edge

 {

     int from, to, cap, flow;

 };

 bool operator < (const Edge& a, const Edge& b)

 { return a.from < b.from || ( a.from == b.from && a.to < b.to ); }

 struct Dinic

 {

     int n, m, s, t;

     vector<Edge> edges;

     vector<int> G[maxn];

     bool vis[maxn];    //BFS

     int d[maxn];    //起点到i的距离

     int cur[maxn];    //当前弧指针

     int Init(int n)

     {

         for(int i = ; i < n; ++i) G[i].clear();

         edges.clear();

     }

     void AddEdge(int from, int to, int cap)

     {

         edges.push_back(Edge{from, to, cap, });

         edges.push_back(Edge{to, from, , });

         m = edges.size();

         G[from].push_back(m-);

         G[to].push_back(m-);

     }

     bool BFS()

     {

         memset(vis, false, sizeof(vis));

         queue<int> Q;

         Q.push(s);

         vis[s] = true;

         d[s] = ;

         while(!Q.empty())

         {

             int x = Q.front(); Q.pop();

             for(int i = ; i < G[x].size(); ++i)

             {

                 Edge& e = edges[G[x][i]];

                 if(!vis[e.to] && e.cap > e.flow)

                 {

                     vis[e.to] = true;

                     d[e.to] = d[x] + ;

                     Q.push(e.to);

                 }

             }

         }

         return vis[t];

     }

     int DFS(int x, int a)

     {

         if(x == t || a == ) return a;

         int flow = , f;

         for(int& i = cur[x]; i < G[x].size(); ++i)

         {

             Edge& e = edges[G[x][i]];

             if(d[x] +  ==d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > )

             {

                 e.flow += f;

                 edges[G[x][i]^].flow -= f;

                 flow += f;

                 a -= f;

                 if(a == ) break;

             }

         }

         return flow;

     }

     int MaxFlow(int s, int t)

     {

         this->s = s; this->t = t;

         int flow = ;

         while(BFS())

         {

             memset(cur, , sizeof(cur));

             flow += DFS(s, INF);

         }

         return flow;

     }

 }g;

 int w, h;

 char pool[][];

 inline int ID(int i, int j) { return i*w+j; }

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int T, d, f, b;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d%d%d%d%d", &w, &h, &d, &f, &b);

         for(int i = ; i < h; ++i) scanf("%s", pool[i]);

         int cost = ;

         for(int i = ; i < h; ++i)//把边上的洞填成草

         {

             if(pool[i][] == '.') { pool[i][] = '#'; cost += f; }

             if(pool[i][w-] == '.') { pool[i][w-] = '#'; cost += f; }

         }

         for(int i = ; i < w; ++i)

         {

             if(pool[][i] == '.') { pool[][i] = '#'; cost += f; }

             if(pool[h-][i] == '.') { pool[h-][i] = '#'; cost += f; }

         }

         g.Init(h*w+);

         for(int i = ; i < h; i++)

             for(int j = ; j < w; j++)

             {

                 if(pool[i][j] == '#')

                 {

                     int cap = d;

                     if(i ==  || i == h- || j ==  || j == w-) cap = INF;

                     g.AddEdge(w*h, ID(i, j), cap);

                 }

                 else

                 {

                     g.AddEdge(ID(i, j), w*h+, f);

                 }

                 if(i > ) g.AddEdge(ID(i, j), ID(i-, j), b);

                 if(i < h-) g.AddEdge(ID(i, j), ID(i+, j), b);

                 if(j > ) g.AddEdge(ID(i, j), ID(i, j-), b);

                 if(j < w-) g.AddEdge(ID(i, j), ID(i, j+), b);

             }

         printf("%d\n", cost + g.MaxFlow(w*h, w*h+));

     }

     return ;

 }