Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4128
0689

Time Limit: 1 Second      Memory Limit: 65536 KB

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 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$: $$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}$$

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

Input

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$.

Output

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.

Sample Input

2
0689
08

Sample Output

8
2

Hint

We hereby explain the first sample test case.

Substring Result Substring Result
0 0689 68 0899
6 0989 89 0668
8 0689 068 8909
9 0686 689 0689
06 9089 0689 6890

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
Submit    Status