#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;

int inf = 1e9+7;

int n ,m;

char board[105][105];
bool key[130];
bool visited[105][105];
vector<pair<int, int>> pos[130];
int dx[] = {1, -1, 0, 0}, dy[] =  {0, 0, 1, -1};


int solution(){
    queue<pair<int, int>> q;
    
    q.push({0, 0});
    visited[0][0] = true;
    
    int result = 0;
    
    while(!q.empty()){
        auto [y, x] = q.front(); q.pop();
        
        if(board[y][x] == '$') result++;
        
//        cout << board[y][x] << "\n";
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            
            if(0 <= ny && ny <= n+2 && 0 <= nx && nx <= m+2 && board[ny][nx] != '*' && !visited[ny][nx]){
                visited[ny][nx] = true;
                if('a' <= board[ny][nx] && board[ny][nx] <= 'z'){
                    key[board[ny][nx]] = true;
                    for(pair<int, int> door : pos[board[ny][nx] - 'a' + 'A']){
                        if(visited[door.first][door.second]) q.push(door);
                    }
                    
                    
                }
                
                else if('A' <= board[ny][nx] && board[ny][nx] <= 'Z' && !key[board[ny][nx] + 'a' - 'A']) continue;
                
                q.push({ny, nx});
                
            }
            
        }
        
    }
//    cout << '\n';
//    for(int i = 0; i <= n+1; i++){
//        for(int j = 0; j <= m+1; j++) cout << visited[i][j] << " ";
//        cout << '\n';
//    }
    
    return result;;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    
    
    
    while(t-->0){
        cin >> n >> m;
        
        for(int i = 0; i < 105; i++){
            for(int j = 0; j < 105; j++) {
                board[i][j] = '.';
                visited[i][j] = false;
            }
        }
        
        
        for(int i = 0; i < 131; i++){
            pos[i].clear();
            key[i] = false;
        }
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> board[i][j];
                
                if('A' <= board[i][j] && board[i][j] <= 'Z') pos[board[i][j]].push_back({i, j});
                
            }
        }
        
        string keys;
        cin >> keys;
        
        for(char k : keys) key[k] = true;
        
        
        
        
        cout << solution() << "\n";
        
        
        
        
    }
    
    
    
    
    return 0;
}