题目描述

在一个只有大写字母的字符串 $s$ 中，如果存在位置 $i<j$ 且 $s[i]=s[j]$ ，则称 $(i,j)$ 为字符串 $s$ 中的一个​字符对​。

然而，如果存在位置 $i<j$ 且 $s[i]\ne s[j]$ ，则称 $(i,j)$ 为字符串 $s$ 中的一个​字符错​。

翁老师的字符串有点不一样，它可能含有一些字符 ? 。

• 当字符 ? 出现时，它有可能是任何一个大写字母（同一时刻只能看作一个）。

现在给你一个字符串，请你求出这个字符串中不同的 字符错 的​最大个数​。

对于两个 字符错，只要它们的 $i$ 位置不同或 $j$ 位置不同，我们就认为这两个 字符错 是​ 不同的​。

此外，翁老师为了检验你对此题的理解程度，他会询问你 $t$ 次。

输入格式

第一行一个整数 $t$ ，表示询问次数。

• 接下来 $t$ 行每行一个字符串 $s$ 。$s$ 只包含大写英文字母和 ? 。

输出格式

输出 $t$ 行，每行一个整数，表示不同字符错的最大个数。

3
YIYISIWUYISI
YIJIUYIJIUBAYILING
YIYISIWUYISIYIJIUYIJIUBAYILING

52
133
360

5
NI?IQ?O?CRXO?XQH?J?R
??ZPJ??O?Z??ZPPVQ?I?
INUX??AOJKI?YJYWVF?I
I?FM?X?O?QC???XUX?KI
?F??L??GTB??QWYBIUOQ

185
184
185
186
188

1
????CCF

20

数据规模与约束

对于 $20\%$ 的数据，$|s|\le 100$；

对于 $40\%$ 的数据，$|s|\le 1000$；

对于另外 $20\%$ 的数据，所有的 $s$ 中都不包含 ? ；

对于另外 $10\%$ 的数据，$s$ 只包含 ?；

对于 $100\%$ 的数据，$1\leq t\leq 10,1\leq |S|\leq 10^6$。