题目描述

给定一个边长为 \(n\) 的三维网格，在所有整数坐标点 \((x,y,z)\)（其中 \(1 \le x,y,z \le n\)）上各放置一个字母，字母只能是 B、A、P、C 四种之一。

我们称一组四个点构成一个“弯曲单词 BAPC”，当且仅当它们满足：

1. 这四个点上的字母按顺序分别是 B、A、P、C；
2. 三点 B-A-P 形成的夹角是 \(90^\circ\)，也就是向量 \(\overrightarrow{BA}\) 与 \(\overrightarrow{AP}\) 垂直；
3. 三点 A-P-C 形成的夹角是 \(90^\circ\)，也就是向量 \(\overrightarrow{AP}\) 与 \(\overrightarrow{PC}\) 垂直。

注意：

• 这两个直角不要求与坐标轴对齐；
• 四个点只要满足以上几何条件即可。

请你计算，这个三维网格中一共有多少个“弯曲单词 BAPC”。

输入格式

第一行一个整数 \(n\)：

• \(1 \le n \le 22\)

之后输入 \(n\) 个块，每个块有 \(n+1\) 行：

• 第一行是一个单独的连字符 -，仅用于提高可读性；
• 接下来的 \(n\) 行，每行一个长度为 \(n\) 的字符串，只包含 B、A、P、C，表示三维网格中的一层。

也就是说，整个输入描述了 \(n\) 个水平层，每层是一个 \(n \times n\) 的字母网格。

输出格式

输出一个整数，表示弯曲单词 BAPC 的总数。

样例输入 1

1
-
B

样例输出 1

0

样例输入 2

2
-
PA
PB
-
CC
PB

样例输出 2

2

样例输入 3

3
-
BBB
BCB
BCB
-
BBC
CBA
BBB
-
BBB
BPB
BBB

样例输出 3

2