题目描述

又是难得的体育课，又是找不到体育老师的一天，贪玩的小鹿决定去寻找体育老师，热爱学习的你决定去阻止他。

已知小鹿寻找体育老师的过程可以抽象成在一张 $n \times n$ 的地图上。

小鹿在左上角坐标值 $(1,1)$ 的起点 $s$ 处，体育老师在右下角坐标值 $(n,n)$ 的终点 $t$ 处,路上的格子上也许存在着障碍物，如果这个格子上有障碍物就用 $x$ 表示，如果没有障碍物就用 $.$ 表示。小鹿无法通过存在障碍物的格子。

现在你可以在任意 $.$ 处放置障碍物来阻止小鹿，但是你怕麻烦，那么你最少可以放置多少个障碍物来阻止小鹿呢？

注意：小鹿只能上下左右移动，不能斜着移动，也不能移动到地图外面去。保证起点和终点处无障碍物，且不能放置障碍物。

输入格式

第一行一个整数 $n$ $(2 \leq n \leq 4)$ 。

接下来 $n$ 行，每行有 $n$ 个字符，表示抽象出来的地图 $map$ 。保证 $map_{i,j} \in \{'s','t','x','.'\}$ 。

输出一行一个整数，表示最少需要放置的障碍物数。

4
s...
..x.
..x.
..xt

3
sxx
x..
..t

对于样例 $1$ ，你只需要在 $(1,3),(1,2),(1,4),(3,4)$ 任意一个位置放置一个障碍物，小鹿都找不到体育老师。

样例 $2$ 小鹿本来就找不到体育老师，所以输出 $0$ 。