def is_valid_move(position, grid):
    # Check if the position is within the grid and not hitting a wall or hazard
    r, c = position
    R, C = len(grid), len(grid[0])
    return 0 <= r < R and 0 <= c < C and grid[r][c] != '#' and grid[r][c] != '*'

def simulate_movement(start, finish, grid):
    R, C = len(grid), len(grid[0])
    # Initialize probabilities with 0 for all positions
    dp = [[0.0 for _ in range(C)] for _ in range(R)]
    sr, sc = start
    fr, fc = finish
    dp[sr][sc] = 1.0 # Initial probability of starting position is 1

    # Define possible movements in each direction
    dr = [-1, 1, 0, 0] # North, South, East, West
    dc = [0, 0, 1, -1]

    # Iterate through each step until reaching the finish position or cannot move anymore
    while True:
        new_dp = [[0.0 for _ in range(C)] for _ in range(R)] # Store updated probabilities for each position
        updated = False # Flag to check if any probability has been updated in this step
        for r in range(R):
            for c in range(C):
                # Skip if hitting a wall or hazard
                if grid[r][c] == '#' or grid[r][c] == '*':
                    continue

                # Iterate through all possible voice commands (north, south, east, west)
                for d in range(4):
                    nr, nc = r + dr[d], c + dc[d]
                    if is_valid_move((nr, nc), grid):
                        # Update the probability of reaching the new position
                        # with equal probability of choosing north or south, east or west
                        new_dp[nr][nc] += 0.5 * dp[r][c]
                        new_dp[r][c] += 0.5 * dp[r][c]
                        updated = True

                    # Check if reached the finish position with probability at least 1-10^(-10100)
                    if (r, c) == start and (nr, nc) == finish and new_dp[nr][nc] >= 1 - 10 ** (-10100):
                        return True

        # Update the probabilities for the next step
        dp = new_dp

        # If no probability has been updated in this step, break the loop
        if not updated:
            break

    return False

def find_drivable_pairs(test_cases):
    results = []
    for i, (R, C, grid) in enumerate(test_cases):
        drivable_pairs = []
        #