It is the 25th of December, 2025. As a Christmas tradition, you gather a group of friends to solve a puzzle. Among your friends are wordcels and shape rotators, who are respectively better at thinking with words and with mental images. This puzzle challenges even the smartest wordcel and the most brilliant shape rotator:
There is a $$$3$$$-dimensional grid with points at all integer coordinates $$$(x,y,z)$$$ with $$$1\leq x,y,z\leq n$$$, and each point has a label associated with it, which is either 'B', 'A', 'P', or 'C'. In this grid, you need to find occurrences of the curly word "BAPC". A curly word "BAPC" is a collection of four points in the grid such that:
- The labels spell out "BAPC" (in this order).
- The angle that the triplet "BAP" makes is $$$90$$$ degrees: the vectors from $$$\texttt{B}\to \texttt{A}$$$ and from $$$\texttt{A}\to \texttt{P}$$$ form a $$$90$$$-degree angle.
- The angle that the triplet "APC" makes is $$$90$$$ degrees: the vectors from $$$\texttt{A}\to \texttt{P}$$$ and from $$$\texttt{P}\to \texttt{C}$$$ form a $$$90$$$-degree angle.
Note that the two angles do not need to be axis-aligned. As an example, see the third sample case, visualized in the Notes section.
How many occurrences of the curly word "BAPC" are in the given grid?
The input consists of:
- One line with an integer $$$n$$$ ($$$1\leq n\leq 22$$$), the size of the grid.
- $$$n$$$ blocks of $$$n+1$$$ lines. Each block of $$$n+1$$$ lines consists of:
- One line with a hyphen (-), to make the input more human-readable.
- $$$n$$$ lines with $$$n$$$ characters, each character being either 'B', 'A', 'P', or 'C', representing all labels of one horizontal layer of the $$$3$$$-dimensional grid.
Output the number of curly words "BAPC" in the $$$3$$$-dimensional grid.
1-B
0
2-PAPB-CCPB
2
3-BBBBCBBCB-BBCCBABBB-BBBBPBBBB
2
Visualization of the third sample input. In this grid, there are two curly words "BAPC", using the highlighted letters.
