Problem5151--网格画

5151: 网格画

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

黑白世界最近比较流行网格画,网格画就是把正方形画布分成 n \times n × n 个大小相同的正方形网格,然后把某些格子涂成黑色,其余格子保持原来的白色

比如下面四幅画作都是 n = 4 4 的网格画:


 

 


不难发现,第一幅画顺时针旋转 90\degree, 180\degree, 270\degree 90°180°270° 分别可以得到后面的三幅画

现在给定两幅画作,请你判断第一幅画作至少顺时针旋转多大角度可以得到第二幅画作。

Input

输入包含 TT 组测试数据,第一行先输入测试数据组数 TT,接下来,对于每组测试数据:

第一行,仅包含一个正整数 nn,表示下面给出的网格画包含 nn 行 nn 列

接下来 nn 行描述一幅网格画,每有行一个长度为 nn 的字符串,其中每个字符要么是 BB,要么是 WWBB 代表黑色格子,WW 代表白色格子。

接下来 nn 行描述另一幅网格画,每有行一个长度为 nn 的字符串,其中每个字符要么是 BB,要么是 WWBB 代表黑色格子,WW 代表白色格子。

Output

对于每组测试数据,输出单独的一行,包含一个非负整数 dd,表示第一幅画作最少顺时针旋转 d\degreed° 能得到第二幅画作,如果第一幅画作无论如何旋转都得不到第二幅,请输出 -11。

Sample 1 Input

3
1
B
W
2
BB
WW
BB
WW
4
BBWW
WBWB
WWBW
BWWB
BWWB
WWBB
WBWW
BWBW

Sample 1 Output

-1
0
90

HINT

【数据范围】

本题共包含四个测试点,

第一个测试点,T = 4, n = 1 41

第二个测试点,T = 256, n = 2 2562

第三个测试点,T = 10, n \leq 500 10≤ 500,保证答案一定不为 -11 且不超过 9090

第四个测试点, T = 10, n \leq 500 10≤ 500

Source/Category