如果一个字符串仅由数字 ‘0’、‘6’、‘8’ 和 ‘9’ 组成，我们称其为 0689-字符串。给定一个长度为 $n$ 的 0689-字符串 $s$，必须执行且仅执行一次以下操作：选择 $s$ 的一个非空子串并将其旋转 180 度。

更正式地说，设 $s_i$ 为字符串 $s$ 的第 $i$ 个字符。在将从 $s_l$ 开始到 $s_r$ 结束的子串（$1 \le l \le r \le n$）旋转 180 度后，字符串 $s$ 将变为字符串 $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$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示执行该操作恰好一次后可以得到的不同字符串的数量。

样例

输入格式 1

2
0689
08

输出格式 1

8
2

说明

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

很容易发现，在操作后我们可以得到 8 种不同的字符串。