P9642 [SNCPC2019] 0689

我们称一个字符串为 0689-字符串，如果这个字符串只包含数字 0、6、8 和 9。给定一个长度为 $n$ 的 0689-字符串 $s$，必须执行以下操作一次：选择 $s$ 的一个非空子串并将其旋转 180 度。 更正式地说，设 $s_i$ 为字符串 $s$ 的第 $i$ 个字符。在将从 $s_l$ 开始到 $s_r$ 结束的子串旋转180度后 ($1 \le l \le r \le n$)，字符串 $s$ 将变成长度为 $n$ 的字符串 $t$，其通过以下公式得到，其中 $t_i$ 表示字符串 $t$ 中的第 $i$ 个字符： $$t_i = \begin{cases} s_i & \text{if } 1 \le i < l \text{ or } r < i \le n \\ \text{`0'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`0'} \\ \text{`6'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`9'} \\ \text{`8'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`8'} \\ \text{`9'} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \text{`6'} \\ \end{cases}$$ 经过这个操作后，可以得到多少个不同的字符串？

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： - 第一行且唯一一行包含一个 0689-字符串 $s$ ($1 \le |s| \le 10^6$)。 保证所有测试用例的 $|s|$ 之和不超过 $10^7$。

对于每个测试用例输出一行，包含一个整数，表示经过一次操作可以得到的不同字符串的数量。 **【样例解释】** 我们在此解释第一个样例测试用例。 $$\begin{array}{|c|c||c|c|}\hline \textbf{子串} & \textbf{结果} & \textbf{子串} & \textbf{结果} \\ \hline 0 & 0689 & 68 & 0899 \\ \hline 6 & 0989 & 89 & 0668 \\ \hline 8 & 0689 & 068 & 8909 \\ \hline 9 & 0686 & 689 & 0689 \\ \hline 06 & 9089 & 0689 & 6890 \\ \hline \end{array}$$ 很容易发现，经过这个操作可以得到 8 个不同的字符串。 翻译来自于：[ChatGPT](https://chatgpt.com/)。

We hereby explain the first sample test case. $$\begin{array}{|c|c||c|c|}\hline \textbf{Substring} & \textbf{Result} & \textbf{Substring} & \textbf{Result} \\ \hline 0 & 0689 & 68 & 0899 \\ \hline 6 & 0989 & 89 & 0668 \\ \hline 8 & 0689 & 068 & 8909 \\ \hline 9 & 0686 & 689 & 0689 \\ \hline 06 & 9089 & 0689 & 6890 \\ \hline \end{array}$$ It's easy to discover that we can get $8$ different strings after the operation.