from collections import deque

T = int(input())

for t in range(1, T+1):
    R, C = map(int, input().split())
    grid = [input().strip() for _ in range(R)]
    
    # Find all starting and finishing points
    starts = {}
    finishes = {}
    for i in range(R):
        for j in range(C):
            if grid[i][j].islower():
                starts[grid[i][j]] = (i, j)
            elif grid[i][j].isupper():
                finishes[grid[i][j]] = (i, j)
    
    # Build a graph of drivable positions
    graph = {}
    for i in range(R):
        for j in range(C):
            if grid[i][j] == '#':
                continue
            pos = (i, j)
            graph[pos] = []
            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ni, nj = i+di, j+dj
                if ni < 0 or ni >= R or nj < 0 or nj >= C:
                    continue
                if grid[ni][nj] == '#':
                    continue
                graph[pos].append((ni, nj))
    
    # Memoization table for simulations
    memo = {}
    
    # Perform DFS simulations for each start/finish pair
    drivable_pairs = []
    for s, sp in starts.items():
        for f, fp in finishes.items():
            if s == f:
                continue
            key = (sp, f)
            if key in memo:
                if memo[key]:
                    drivable_pairs.append(s+f)
                continue
            memo[key] = False
            
            # DFS simulation with memoization
            stack = deque([(sp, 0, None)])
            while stack:
                pos, steps, prev_dir = stack.pop()
                if steps > 100:
                    break
                if pos == fp:
                    memo[key] = True
                    drivable_pairs.append(s+f)
                    break
                if grid[pos[0]][pos[1]] == '*':
                    break
                for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    ni, nj = pos[0]+di