将城市从外星入侵者手中解放出来的战斗结束了！人们很高兴，爱与和平又回来了。

城市被表示为一个有 $R$ 行 $C$ 列的网格。网格中的一些单元格是建筑物（没人能看见、没人能射击、也没人能走过），另一些是街道（每个人都能看见、射击和走过）。不幸的是，在战争期间，现在已被击败的入侵者在城市中设置了自动安全炮塔。这些炮塔只存在于街道上（不在建筑物内）。它们对市民构成威胁，但幸运的是，街道上也有一些士兵（不在建筑物内）。最初，没有士兵与炮塔处于同一位置。

入侵者炮塔不会移动。它们很小，所以不会阻挡视线和射击。士兵不能穿过激活的炮塔所在的单元格，但可以在炮塔被摧毁后穿过它。炮塔只能看到处于其水平或垂直视线范围内的单元格中的士兵。如果士兵进入这样的单元格，炮塔不会开火。如果士兵试图离开这样的单元格（在进入后，或从该单元格开始），炮塔就会开火。幸运的是，士兵仍然可以从该单元格射击，而炮塔不会将其检测为移动。这意味着你的士兵实际上都不会死亡，因为在最坏的情况下，他们总是可以静止不动地等待救援（可能需要很长时间）。也许你以后还有机会营救他们。

每个士兵总共可以进行 $M$ 次单位移动。这些移动中的每一次都必须是水平或垂直方向上的一个单元格。士兵可以互相穿过，并且不会阻挡其他士兵或炮塔的视线。每个士兵还有一颗子弹。如果士兵的水平或垂直视线范围内有炮塔，士兵可以射击并摧毁它。每次射击只能摧毁一个炮塔，但士兵们是如此出色的射手，以至于他们甚至可以射穿视线中的一个或多个炮塔或士兵，击中更远处的另一个炮塔！

你将获得一张地图（标有士兵和炮塔的位置）。士兵们能摧毁的炮塔的最大数量是多少？

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以一行开始，包含整数 $C$（地图宽度）、$R$（地图高度）和 $M$（每个士兵可以进行的单位移动次数）。接下来的 $R$ 行包含 $C$ 个字符，其中 . 代表街道，# 代表建筑物，S 代表士兵，T 代表炮塔。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是可能摧毁的炮塔的最大数量。然后输出 $y$ 行：每行应包含两个整数 $s_i$ 和 $t_i$，表示发生的第 $i$ 件事是士兵 $s_i$ 摧毁了炮塔 $t_i$（你不需要具体说明士兵必须如何移动）。如果存在多种有效的策略，你可以输出其中任何一种。

士兵的编号方式为：从顶行开始，从左到右，然后是下一行从左到右，依此类推，从上到下。炮塔使用它们自己独立的编号，并以同样的方式从 1 开始编号。

数据范围

内存限制：1 GB。 $1 \le T \le 100$。 $0 \le M < C \times R$。

子任务 1

时间限制：15 秒。 $1 \le C \le 30$。 $1 \le R \le 30$。 S 符号的数量在 1 到 10 之间。 T 符号的数量在 1 到 10 之间。

子任务 2

时间限制：30 秒。 $1 \le C \le 100$。 $1 \le R \le 100$。 S 符号的数量在 1 到 100 之间。 T 符号的数量在 1 到 100 之间。

样例

样例输入 1

4
2 2 1
#S
T.
2 6 4
.T
.T
.T
S#
S#
S#
5 5 4
.....
SS#.T
SS#TT
SS#.T
.....
3 3 8
S.#
.#.
#.T

样例输出 1

Case #1: 1
1 1
Case #2: 3
3 3
1 1
2 2
Case #3: 3
1 2
2 1
6 3
Case #4: 0

说明

在样例 2 中，一种可能的解决方案是让士兵 3 向上移动三个单元格并射击炮塔 3。然后士兵 1 可以向上移动一个单元格并向右移动一个单元格（到达炮塔 3 原来的位置）并射穿炮塔 2 以摧毁炮塔 1。最后，士兵 2 可以向上移动三个单元格并射击炮塔 2。

在样例 3 中，士兵 1 可以向上移动一个单元格，然后向右移动三个单元格并射击炮塔 2。然后士兵 2 可以向上移动一个单元格，然后向右移动三个单元格并射击炮塔 1。最后，士兵 6 可以向下移动一个单元格，然后向右移动三个单元格并射击炮塔 3。其他士兵的移动范围不足以射击任何其他炮塔。

在样例 4 中，士兵无法移动到与炮塔相同的行或列，因此无法摧毁炮塔。