题目描述

在一段字符记录中，部分字符可能暂时无法辨认，并使用通配符 ? 表示。

给定一个字符串 $S$，其中 $S_i$ 表示字符串从左向右数第 $i$ 个字符，下标从 $1$ 开始。

例如，当 $S=\texttt{abcd}$ 时，$S_2=\texttt{b}$。

字符串的子串是从原字符串中选取一段下标连续的字符所得到的字符串。例如，$\texttt{abc}$ 是 $\texttt{abcd}$ 的子串，而 $\texttt{acd}$ 不是。

对于两个字符 $x$ 和 $y$，当它们满足以下任意一个条件时，称它们可以匹配：

• $x=y$；
• $x$ 和 $y$ 中至少有一个字符是通配符 ?。

对于一个长度为 $|t|$ 的字符串 $t$，如果对于所有满足 $1\leq i\leq |t|$ 的位置 $i$，字符 $t_i$ 都能与字符 $t_{|t|-i+1}$ 匹配，那么称 $t$ 为一个模糊镜像串。

换句话说，从字符串两端向中间依次比较时，每一对对应字符必须相同，或者其中至少有一个字符为 ?。

请统计字符串 $S$ 的所有子串中，有多少个子串是模糊镜像串。

两个子串即使内容相同，只要它们在原字符串中的位置不同，也应分别计数。

输入格式

每个测试点中包含多组测试数据。

第一行输入一个整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行输入一个字符串 $S$，表示一组测试数据。

输出格式

对于每组测试数据，输出一行一个整数，表示字符串 $S$ 中模糊镜像子串的数量。

2
tt
a?ab

3
8

样例 1 解释

对于测试数据 1，$S=\texttt{tt}$，其镜像子串如下：

$\texttt{\underline{t}t}$，$\texttt{t\underline{t}}$，$\texttt{\underline{tt}}$

共 3 个。

对于测试数据 2，$S=\texttt{a?ab}$，其镜像子串如下：

$\texttt{\underline{a}?ab}$，$\texttt{a\underline{?}ab}$，$\texttt{a?\underline{a}b}$，$\texttt{a?a\underline{b}}$，$\texttt{\underline{a?}ab}$，$\texttt{a\underline{?a}b}$，$\texttt{\underline{a?a}b}$，$\texttt{a\underline{?ab}}$

共 8 个。

数据范围

对于 $100$ 的测试数据：

• $1 \le T \le 10$
• $1 \le |S| \le 500$
• $S$ 仅由小写英文字母与通配符 ? 组成

特殊性质：

• 对于 $40$ 的测试数据，$S$ 不含通配符 ?。