普及模拟赛 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$​​ 的长度。

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

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

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