
ZOJ Problem Set  4128
We call a string as a 0689string if this string only consists of digits '0', '6', '8' and '9'. Given a 0689string $s$ of length $n$, one must do the following operation exactly once: select a nonempty 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$: $$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+ri} = \text{'0'} \\ \text{'6'} & \text{if } l \le i \le r \text{ and } s_{l+ri} = \text{'9'} \\ \text{'8'} & \text{if } l \le i \le r \text{ and } s_{l+ri} = \text{'8'} \\ \text{'9'} & \text{if } l \le i \le r \text{ and } s_{l+ri} = \text{'6'} \\ \end{cases}$$ What's the number of different strings one can get after the operation? InputThere 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 0689string $s$ ($1 \le s \le 10^6$). It's guaranteed that the sum of $s$ of all test cases will not exceed $10^7$. OutputFor each test case output one line containing one integer, indicating the number of different strings one can get after applying the operation exactly once. Sample Input2 0689 08 Sample Output8 2 HintWe hereby explain the first sample test case.
It's easy to discover that we can get 8 different strings after the operation. Author: WENG, Caizhi Source: The 2019 ICPC China Shaanxi Provincial Programming Contest 