# Define directions for commands
directions = {'N': (-1, 0), 'S': (1, 0), 'E': (0, 1), 'W': (0, -1)}

# Function to check if a cell is valid and not blocked
def is_valid(r, c, R, C, grid):
    return r >= 0 and r < R and c >= 0 and c < C and grid[r][c] != '#'

# Function to perform DFS traversal on the graph
def dfs(r, c, prob, grid, visited, graph, finish_cells, drivable_pairs):
    if (r, c) in finish_cells:
        drivable_pairs.add((grid[start_r][start_c], grid[r][c])) # Add drivable pair
    visited.add((r, c))
    for command, (dr, dc) in directions.items():
        new_r, new_c = r + dr, c + dc
        if is_valid(new_r, new_c, R, C, grid):
            # Check for mishearing commands and update probability
            if (new_r, new_c) not in visited:
                dfs(new_r, new_c, prob * 0.5, grid, visited, graph, finish_cells, drivable_pairs)
            # Add edge and reverse edge to graph
            graph[(r, c)].add((new_r, new_c))
            graph[(new_r, new_c)].add((r, c))

# Read number of test cases
T = int(input())

# Iterate over test cases
for t in range(1, T + 1):
    R, C = map(int, input().split()) # Read grid size
    grid = [input().strip() for