题目描述

小 C 有一个能量魔方，这个魔方可神奇了，只要按照特定方式，放入不同的能量水晶，就可以产生巨大的能量。

能量魔方是一个 $n \times n \times n$ 的立方体，一共用 $n^3$ 个空格可以填充能量水晶。

能量水晶有两种：

• 一种是正能量水晶（Positive）
• 一种是负能量水晶（Negative）

当这个魔方被填满后，就会依据填充的能量水晶间的关系产生巨大能量。对于相邻两（相邻就是拥有同一个面）的两个格子，如果这两个格子填充的是一正一负两种水晶，就会产生一单位的能量。而整个魔方的总能量，就是这些产生的能量的总和。

现在，小 C 已经在魔方中填充了一些水晶，还有一些位置空着。他想知道，如果剩下的空格可以随意填充，那么在最优情况下，这个魔方可以产生多少能量。

输入格式

第一行包含一个数 $n$，表示魔方的大小。

接下来 $n^2$ 行，每行 $n$ 个字符，每个字符有三种可能：

• P：表示此方格已经填充了正能量水晶；
• N：表示此方格已经填充了负能量水晶；
• ?：表示此方格待填充。

上述 $n^2$ 行，第 $(i-1) \times n+1$ 到第 $i \times n$ 行描述了立方体第 i 层从前到后，从左到右的状态。且每 $n$ 行间，都有一空行分隔。

输出格式

仅包含一行一个数，表示魔方最多能产生的能量。

2
P?
??

??
N?

9

样例说明 1

如下状态时，可产生最多的能量。

PN
NP

NP
NN

数据规模与约定

• 对于 $10\%$ 的数据，$n \leq 3$；
• 对于 $30\%$ 的数据，$n \leq 4$；
• 对于 $80\%$ 的数据，$n \leq 10$；
• 对于 $100\%$ 的数据，$n \leq 40$。