Maze Path Existence

You are given a 2D maze represented as a grid of characters. Your task is to determine whether there exists a path from the starting cell marked S to the goal cell marked G. The maze is composed of the following characters:

• S: Starting cell
• G: Goal cell
• .: Open path
• #: Wall/Obstacle

You are allowed to move in the four cardinal directions (up, down, left, right). If either the start or goal is missing, or if no valid path exists between S and G, output "No Path". Otherwise, output "Path Exists".

This problem can be solved using graph traversal algorithms such as breadth-first search (BFS) or depth-first search (DFS). In mathematical notation, if we let \(G(V,E)\) be the graph representation of the maze, then we need to determine if there exists a path between nodes \(s\) and \(g\), where \(s\) and \(g\) correspond to the positions of 'S' and 'G' respectively.

inputFormat

The input begins with an integer T (1 ≤ T ≤ 100) on a single line representing the number of mazes. For each maze, the first line contains two space-separated integers R and C (1 ≤ R, C ≤ 100) representing the number of rows and columns respectively. This is followed by R lines, each containing a string of length C representing a row of the maze.

outputFormat

For each maze, output a single line: Path Exists if there is a valid path from 'S' to 'G', otherwise No Path. The output for each test case should be printed on a new line.

## sample

1
3 4
S...
.#..
..G.

Path Exists

</p>