题目描述

We call a string as a 0689-string if this string only consists of digits 0, 6, 8 and 9. Given a 0689-string $s$ of length $n$, one $\textbf{must}$ do the following operation exactly once: select a non-empty substring of $s$ and rotate it 180 degrees.

More formally, let $s_i$ be the $i$-th character in string $s$. After rotating the substring starting from $s_l$ and ending at $s_r$ 180 degrees ($1 \le l \le r \le n$), string $s$ will become string $t$ of length $n$ extracted from the following equation, where $t_i$ indicates the $i$-th character in string $t$:

What's the number of different strings one can get after the operation?

输入格式

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and only line contains a 0689-string $s$ ($1 \le |s| \le 10^6$).

It's guaranteed that the sum of $|s|$ of all test cases will not exceed $10^7$.

输出格式

For each test case output one line containing one integer, indicating the number of different strings one can get after applying the operation exactly once.

题目大意

【题目描述】

我们称一个字符串为 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$，表示测试用例的数量。对于每个测试用例：

• 第一行且唯一一行包含一个 0689-字符串 $s$ ($1 \le |s| \le 10^6$)。 保证所有测试用例的 $|s|$ 之和不超过 $10^7$。

【输出格式】

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

【样例解释】

我们在此解释第一个样例测试用例。

很容易发现，经过这个操作可以得到 8 个不同的字符串。

翻译来自于：ChatGPT。

2
0689
08

8
2

提示

We hereby explain the first sample test case.

It's easy to discover that we can get $8$ different strings after the operation.