#MX177. 异组对

异组对

时间限制:1000ms

空间限制:512MB

题目描述

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

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

两个异组对不同,当且仅当它们的 ii 或 jj 不同。

输入格式

第一行一个整数 TT ,表示字符串数量。

接下来 TT 行,每行一个字符串 ss。

输出格式

TT 行,每行一个整数,表示不同“异组对”的最大个数。

样例 1 输入

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

样例 1 输出

84
91

其他样例见下发文件。

数据规模与约定

令 ∣s∣|s| 为 ss​​ 的长度。

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

特殊性质A:所有的 ss 中都不包含 *。

特殊性质B:ss 只包含 *。

对于 100%100\% 的数据,1≤T≤101≤T≤10,1≤∣s∣≤1061≤|s|≤10^6。