from collections import deque
from heapq import heappop, heappush

def solve_case(case_num, grid):
    R, C = len(grid), len(grid[0])
    starts = {}
    finishes = {}
    for r in range(R):
        for c in range(C):
            cell = grid[r][c]
            if cell.islower():
                starts[cell] = (r, c)
            elif cell.isupper():
                finishes[cell] = (r, c)

    drivable_pairs = []
    for start, (sr, sc) in starts.items():
        probs = [[[0.0]*4 for _ in range(C)] for _ in range(R)]
        visited = [[[False]*4 for _ in range(C)] for _ in range(R)]
        for i in range(4):
            probs[sr][sc][i] = 1.0

        q = deque([(sr, sc)])
        while q:
            r, c = q.popleft()
            visited[r][c] = [[False]*4 for _ in range(C)]
            for i in range(4):
                for j in range(4):
                    outcome_i = i // 2 if i % 2 == 0 else 1 - i
                    outcome_j = j // 2 if j % 2 == 0 else 1 - j
                    nr, nc = r + outcome_i - outcome_j, c + outcome_j - outcome_i
                    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#":
                        if grid[nr][nc] == "*":
                            continue
                        total_prob = 0.0
                        for k in range(4):
                            command = "NSWE"[k]
                            if k == i or k == j:
                                prob = 0.5
                            else:
                                prob = 0.25
                            if probs[r][c][k] > 0.0:
                                total_prob