SP12245 NATALIAG - Natalia Plays a Game

在学习计算机科学之余，娜塔莉亚常常在圣地亚哥德洛斯卡瓦列罗斯用她在编程奥林匹克竞赛中赢得的 iPad 玩一个经典的迷宫游戏。 迷宫是一个由 $M$ 行 $N$ 列组成的矩形。开放区域用 'O' 表示，而封闭区域用 '\*' 表示。每个区域都是迷宫中的一个 $1 \times 1$ 的小方块。迷宫中会有一个用 '$' 标记的起点和一个用 '#' 标记的终点，起点和终点都是开放区域。 娜塔莉亚可以从一个开放区域向四个方向（北、南、东、西）移动。例如，如果她当前在位置 $(x, y)$，她可以移动到 $(x + 1, y)$、$(x - 1, y)$、$(x, y + 1)$ 或 $(x, y - 1)$。当然，她不能进入封闭区域。 给定一个这样的矩形迷宫，要求计算从起点到终点的最小步数。如果可以到达终点，输出这个步数；如果无法到达，输出 `-1`。

输入包括多行数据。第一行是一个整数 $T$（$1 \le T \le 10^5$），表示测试用例的数量。接下来的每个测试用例的第一行包含两个整数 $M$ 和 $N$（$1 \le M, N \le 100$），分别表示迷宫的行数和列数。接下来的 $M$ 行每行是一个长度为 $N$ 的字符串，描述迷宫的布局，其中仅包含字符 'O'、'\*'、'$' 和 '#'。

对于每个测试用例，输出从起点到终点所需的最少步数。如果无法到达终点，输出 `-1`。 **本翻译由 AI 自动生成**