题目描述

设’$\red{C}$’为猫，’$\red{M}$’为老鼠，’$\red{*}$’为障碍，’$\red{.}$ ’为空地，猫和老鼠在$\red{10}$$\red{\times 10}$的方格中，例如：

$\red{*...*.....}$

$\red{......*...}$

$\red{...*...*..}$

$\red{..........}$

$\red{...*.C....}$

$\red{*.....*...}$

$\red{...*......}$

$\red{..M......*}$

$\red{...*.*....}$

$\red{.*.*......}$

初始时猫和老鼠都面向北方，它们每秒钟各走一格，如果在某一秒末它们在同一格中，那么猫就抓住老鼠了，"对穿"是不算的。猫和老鼠的移动方式相同：平时沿直线走，下一步如果会碰到障碍物或者出界， 就用$\red{1}$秒的时间做一个右转$\red{90}$度。

试计算猫抓住老鼠需要多少秒。

输入格式

第一行为一整数$\red{N，}$表示有$\red{N}$组测试数据。

每组测试数据为$\red{10}$行，格式如题目描述。

输出格式

树出相遇时间$\red{T}$。如果$\red{100}$步内无解，输出$\red{-1}$。

样例

输入样例

1
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......

输出样例

49