题目描述

小君有一个 N * N 的正方形矩阵，每个位置上都有一个大写字母，比如：

JSK

SSS

KSJ

现在小君从这个矩阵的左上角走到右下角，只能向下或者向右走，将经过的字符连接成一个字符串，现在他想知道所有可能的路径中有多少个字符串是回文串。

输入格式

第一行包括一个整数 N，表示矩阵大小，接下来输入一个 N * N 的字母矩阵。

输出格式

输出小君能找到的本质不同的回文串数量。

样例数据

input

3

JSK

SSS

KSJ

output

2

样例解释

数据规模与约定

对于 $100\%$ 的数据，$1 \leq N \leq 18$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$