B 型字符串问题

时间限制：2s

空间限制：256MB

题目描述

如果一个字符串仅由字符c、d、m和n组成，则称其为 $B$ 型字符串。给定长度为 $k$ 的 $B$ 型字符串 $s$，我们必须执行以下操作一次：选择一个非空子串 $s_l$ 到 $s_r$ ，将其完全进行 $B$ 式修改。

正式地，设 $s_i$ 为字符串 $s$ 中的第 $i$ 个字符。在将起始位置为 $s_l$ 、结束位置为 $s_r$ 的子串完全进行 $B$ 式修改（$1 \le l \le r \le n$）后，字符串 $s$ 将变为长度为 $k$ 的字符串 $t$ ，满足下面的等式，其中 $t_i$ 表示字符串 $t$ 中的第 $i$ 个字符：

• $t_i = s_i$，如果 $1 \le i < l$ 或者 $r < i \le n$
• $t_i = 'c'$，如果 $l \le i \le r$ 并且 $s_{l+r-i} = 'c'$
• $t_i = 'd'$，如果 $l \le i \le r$ 并且 $s_{l+r-i} = 'n'$
• $t_i = 'm'$，如果 $l \le i \le r$ 并且 $s_{l+r-i} = 'm'$
• $t_i = 'n'$，如果 $l \le i \le r$ 并且 $s_{l+r-i} = 'd'$

在进行操作后，我们能得到多少不同的字符串？

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行是一个 $B$ 型字符串 $s$ ($1 \le |s| \le 10^6$)。

保证所有测试用例中字符数 $|s|$ 的总和不超过 $10^7$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示在执行一次操作后可以得到的不同字符串数量。

样例 #1

样例输入 #1

2
cdmn
cm

样例输出 #1

8
2

数据范围

对于 50% 的测试数据，满足 $T=1, 1 \le |s| \le 10^3$ ；

对于全部的测试数据，满足 $1 \le |s| \le 10^6$ ，保证所有测试用例中字符数 $|s|$ 的总和不超过 $10^7$。

提示

样例解释：

$$\begin{array}{|c|c||c|c|}\hline \textbf{Substring} & \textbf{Result} & \textbf{Substring} & \textbf{Result} \\ \hline c & cdmn & dm & cmnn \\ \hline d & cnmn & mn & cddm \\ \hline m & cdmn & cdm & mncn \\ \hline n & cdmd & dmn & cdmn \\ \hline cd & ncmn & cdmn & dmnc \\ \hline \end{array} $$

容易发现，在执行操作后，我们可以得到 m 个不同的字符串。