C. 0689
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \lt l \text{ or } r \lt 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.

Example
Input
2
0689
08
Output
8
2
Note

We hereby explain the first sample test case.

SubstringResultSubstringResult
00689680899
60989890668
806890688909
906866890689
06908906896890

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