Background

Special for beginners, ^_^

Description

有一个 $N$ 阶方阵，里面每个元素都是小写字母。

选择任意两个不超过 $N$ 的自然数 $A$ 和 $B$ 。

把方阵的每一行用 rotate() 函数旋转 $A$ ，每一列用 rotate() 函数旋转 $B$ 。

这样一共可以得到 $N\times N$ 个矩阵，问这些矩阵里面有多少个是对称矩阵。

Format

Input

本题包含多（一二不过三）组测试数据。

每组测试数据的第一行是一个不超过 $3000$ 的正整数 $N$ ，表示矩阵大小。

接下来 $N$ 行，给出一个 $N\times N$ 的矩阵。

Output

每行一个答案。

Samples

2
xy
zx

2

Limitation

1s, 1024KiB for each test case.