### 问题描述 给定一个 $n \times n$ 的矩阵，其中 A 代表起点，C 代表终点。起点永远在左上角，终点永远在右下角。 对于矩阵中其余的点，O 代表可以通过，X 代表路障。 我们可以向**上下左右**移动，但是不能斜走，不能走进为路障的点，也不能超出矩阵范围。 我们可以在任意为 O 的点放置路障，求至少放置几个路障能使得从起点出发**无法**走到终点？ ### 输入格式 第一行为一个正整数 $T$，为样例组数。 对于每组样例，第一行为一个正整数 $n$，含义见问题描述。 接下来是一个 $n \times n$ 的矩阵，仅由大写字母 A,C,O,X 构成。 ### 输出格式 输出 $T$ 行，每行一个整数，为放置路障的个数。 ### 样例输入 ```text 2 2 AO OC 5 AOOOO OOOOO OOOOO XOXXX OOOOC ``` ### 样例输出 ```text 2 1 ``` ### 说明 对于第一组样例，显而易见我们需要在所有为 O 的点放置路障。 对于第二组样例，最优的解决的方案之一是在 $(4,2)$ 处放置一个路障。 ### 评测数据规模 对于 $40$% 的评测数据，$1\leq T\leq 100,2 \leq n \leq 50$。 对于其余 $60$% 的评测数据，$T=1,n=5000$。