来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 20 套，第 2 题。原题标号：B；原本地编号：Z4P1-20-B。

题目描述

给定一个只包含大写字母和 * 的字符串 $s$，* 是通配符，每个 * 都可以替换为任意一个大写字母（不能是零或多个）。若存在 $i < j$ 且 $s_i \ne s_j$，则称 $(i,j)$ 为一个“异组对”。

对于 $T$ 个字符串，请你分别求出每个字符串中不同“异组对”的最大可能数量。

两个异组对不同，当且仅当它们的 $i$ 或 $j$ 不同。

输入格式

第一行一个整数 $T$ ，表示字符串数量。

接下来 $T$ 行，每行一个字符串 $s$。

输出格式

$T$ 行，每行一个整数，表示不同“异组对”的最大个数。

2
MENGXIONGXINAO
M*N*X*O*G*I*A*

84
91

其他样例见下发文件。

数据规模与约束

令 $|s|$ 为 $s$​​ 的长度。

| 测试点编号 | $|s|$ | 特殊性质 | | :---------------: | :---------: | :------: | | 1,2,3,4 | $\leq 100$ | 无 | | 5,6,7,8 | $\leq 10^3$ | 无 | | 9,10,11,12 | $\leq 10^6$ | A | | 13,14 | $\leq 10^6$ | B | | 15,16,17,18,19,20 | $\leq 10^6$ | 无 |

特殊性质A：所有的 $s$ 中都不包含 *。

特殊性质B：$s$ 只包含 *。

对于 $100\%$ 的数据，$1≤T≤10$，$1≤|s|≤10^6$。