这是一个交互式问题。

有一个 $n \times m$ 的网格。两个宝箱被埋在网格中两个不同的单元格内。你的任务是找到它们。你可以进行两种类型的操作：

• DIG r c：尝试在单元格 $(r, c)$ 寻找宝箱。交互器会告诉你是否找到了宝箱。
• SCAN r c：从单元格 $(r, c)$ 进行扫描。该操作的结果是从单元格 $(r, c)$ 到两个宝箱所在单元格的曼哈顿距离之和。从单元格 $(r_1, c_1)$ 到单元格 $(r_2, c_2)$ 的曼哈顿距离计算公式为 $|r_1 - r_2| + |c_1 - c_2|$。

你需要在最多 7 次操作内找到宝箱。这包括 DIG 和 SCAN 操作的总次数。为了解决测试用例，你需要在两个藏有宝箱的单元格中至少各调用一次 DIG 操作。

交互

你的程序必须在单次运行中处理多个测试用例。首先，测试系统会写入 $t$ —— 测试用例的数量 ($1 \le t \le 100$)。然后，依次处理 $t$ 个测试用例。

在每个测试用例中，你的程序应首先读取整数 $n$ 和 $m$ ($2 \le n, m \le 16$)。

然后，你的程序可以进行两种类型的查询：

• DIG r c ($1 \le r \le n; 1 \le c \le m$)。如果你找到了宝箱，交互器返回整数 1，否则返回 0。如果你多次尝试在同一个单元格寻找宝箱，结果将为 0，因为宝箱已经被找到。
• SCAN r c ($1 \le r \le n; 1 \le c \le m$)。交互器返回一个整数，该整数是从单元格 $(r, c)$ 到两个宝箱所在单元格的曼哈顿距离之和。即使你已经找到了其中一个宝箱，该和仍会计算两个宝箱的距离。

当你找到两个宝箱后，即你收到了两次 DIG 操作的 1，你的程序应继续处理下一个测试用例，或者如果这是最后一个测试用例，则退出程序。

样例

输入 1

1
2 3
1
1
3
0
1

输出 1

SCAN 1 2
DIG 1 2
SCAN 2 2
DIG 1 1
DIG 1 3