题面描述

你正在一座巨大的博物馆工作，博物馆的展览厅分为多个区域，其中一些区域陈列着易碎且无法移动的艺术品。你作为一名展览策展人，负责将一件艺术品从某个展区移动到另一个特定的展区。博物馆的地面是由一个矩形网格组成，每个区域可以是空的，或者被一件固定的艺术品占据。

在博物馆中，你需要将这件艺术品从它的起始位置 P 移动到目标展区 K。你只能走在空地上，不能经过被艺术品占据的区域。当你站在某个空地，且该区域与艺术品的区域相邻时，你可以推动艺术品，使其移动到另一个空地。

博物馆的地面上有些区域被视为展览区域，这些区域充满了易碎的艺术品，它们无法被移动，你需要绕过它们。

写一个程序，帮助你计算出最少需要推动艺术品多少次，才能将它从起始展区 P 移动到目标展区 K。如果无法移动到目标展区，请输出 NO。

输入格式

输入首先给出测试用例的数量 t，$t\le1000$ 然后是多个测试用例。每个测试用例包含以下内容：

• 一行包含两个正整数 n, m，$n,m\le 100$ 表示博物馆的展区布局为 n x m 的矩阵。
• 接下来有 n 行，每行包含 m 个字符，表示博物馆的布局。字符的含义如下：
  • S 代表艺术品占据的区域（不能通过）；
  • M 代表你（策展人）的起始位置；
  • P 代表艺术品的起始位置；
  • K 代表艺术品的目标位置；
  • w 代表空地。

每个测试用例中，字符 M、P 和 K 都只出现一次。

输出格式

对于每个测试用例，输出：

• 如果艺术品无法到达目标展区，输出 NO；
• 如果可以，输出最少的艺术品移动次数，即推动艺术品穿越展区边界的次数。

样例

1
10 12
SSSSSSSSSSSS
SwwwwwwwSSSS
SwSSSSwwSSSS
SwSSSSwwSKSS
SwSSSSwwSwSS
SwwwwwPwwwww
SSSSSSSwSwSw
SSSSSSMwSwww
SSSSSSSSSSSS
SSSSSSSSSSSS

7