Maze Path Finder

In this problem, you are given a maze represented as a grid. The maze has \(N\) rows and \(M\) columns, and each cell is either open (denoted by .) or blocked (denoted by #). Your task is to determine whether there exists a path from the top-left cell (\(0,0\)) to the bottom-right cell (\(N-1, M-1\)). You can only move vertically or horizontally, and you cannot visit the same cell more than once.

If the first cell or the last cell is blocked, the answer is immediately Not Possible. Otherwise, use a search algorithm (such as depth-first search) to find if a path exists. The answer for each test case is either Possible or Not Possible.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. For each test case, the first line contains two integers \(N\) and \(M\). This is followed by \(N\) lines, each a string of length \(M\) that represents a row of the maze.

outputFormat

For each test case, output a single line with either Possible if a path exists from the top-left to the bottom-right cell or Not Possible if such a path does not exist.

1
2 2
..
..

Possible