import sys
from collections import deque

def solve():
    # Read input
    R, C = map(int, input().split())
    grid = [input() for _ in range(R)]

    # Find interesting starts and finishes
    starts = {}
    finishes = {}
    for i in range(R):
        for j in range(C):
            c = grid[i][j]
            if c.islower():
                starts[c] = (i, j)
            elif c.isupper():
                finishes[c] = (i, j)

    # Define sub-states
    def substate(pos, north, south, east, west):
        return 4 * (pos[0] * C + pos[1]) + 2 * north + south + east + west

    # Build transition matrix
    M = [[0] * (4 * R * C) for _ in range(4 * R * C)]
    for i in range(R):
        for j in range(C):
            if grid[i][j] in "#*":
                # Wall or hazard, no transitions
                for s in range(4):
                    M[substate((i, j), s == 0, s == 1, s == 2, s == 3)][substate((i, j), s == 0, s == 1, s == 2, s == 3)] = 1
            else:
                # Empty cell, compute transitions
                for s in range(4):
                    # Compute possible movements
                    if s == 0:
                        # North
                        ni = i - 1
                        nj = j
                    elif s == 1:
                        # South
                        ni = i + 1
                        nj = j
                    elif s == 2:
                        # East
                        ni = i
                        nj = j +