from collections import deque
from itertools import product

# Define the possible directions and their corresponding coordinate changes
DIRECTIONS = {'north': (-1, 0), 'south': (1, 0), 'east': (0, 1), 'west': (0, -1)}

def is_valid_move(grid, r, c, direction):
    """Checks if the move in the given direction is valid"""
    dr, dc = DIRECTIONS[direction]
    nr, nc = r + dr, c + dc
    if nr < 0 or nr >= len(grid) or nc < 0 or nc >= len(grid[0]):
        return False  # move is outside the grid
    if grid[nr][nc] == '#':
        return False  # move hits a wall
    if grid[nr][nc] == '*':
        return None  # move hits a hazard
    return (nr, nc)  # valid move, return the new position

def simulate_moves(grid, start, end):
    """Simulates all possible moves from start to end"""
    queue = deque([(start, 1)])  # start with probability 1
    visited = set([start])
    while queue:
        pos, prob = queue.popleft()
        if pos == end and prob >= 1 - 10 ** -100:
            return True  # we can reach the end with high enough probability
        for direction in DIRECTIONS.keys():
            new_pos = is_valid_move(grid, pos[0], pos[1], direction)
            if new_pos is None:
                continue  # move hits a hazard
            if new_pos and new_pos not in visited:
                visited.add(new_pos)
                queue.append((new_pos, prob * 0.5))
    return False  # we cannot reach the end with high enough probability

def find_drivable_pairs(grid):
    """Finds all drivable pairs of start and end positions"""
    starts, ends = {}, {}
    for i, row in enumerate(grid):
        for j, cell in enumerate(row):
            if cell.islower():
                starts[cell] = (i, j)
            elif cell.isupper():
                ends[cell] = (i, j)

    drivable_pairs = []
    for start, end in product(starts.keys(), ends.keys()):
        if simulate_moves(grid, starts[start], ends[end]):
            drivable_pairs.append(start + end)
    
    return sorted(drivable_pairs) if drivable_pairs else ["NONE"]

# Read input and run the test cases
T = int(input())
for case in range(1, T + 1):
    R, C = map(int, input().split())
    grid = [input().strip() for _ in range(R)]
    result = find_drivable_pairs(grid)
    print(f"Case #{case}: {' '.join(result)}")