题目描述

小核桃得到一个只由大写字母和问号 ? 组成的字符串，每个 ? 都可以替换成任意一个大写字母。

对于两个位置 $i<j$，如果第 $i$ 个字符和第 $j$ 个字符不同，就称它们构成一对“字符错”。只要 $i$ 或 $j$ 不同，就视为不同的字符错。

请你替换所有的 ?，使得字符串中“字符错”的对数最多。一共有 $T$ 组询问。

输入格式

第一行一个整数 $T$，表示询问组数。

接下来 $T$ 行，每行一个只含大写字母和 ? 的字符串 $S$。

输出格式

输出 $T$ 行，每行一个整数，表示对应字符串中“字符错”的最大对数。

样例

1
A??

3

1
AABB

4

2
??
ABC

1
3

样例解释

样例 1 中，把两个 ? 分别替换成 B、C，得到 ABC，三对位置上的字符都不同，共 $3$ 对。

样例 2 中没有 ?。AABB 中每个 A 与每个 B 都构成一对字符错，共 $2\times2=4$ 对。

样例 3 中，第一组 ?? 替换成两个不同字母，得 $1$ 对；第二组 ABC 三个字符两两不同，得 $3$ 对。

数据范围与约定

对于 $100\%$ 的数据，$1\le T\le 10$，$1\le \lvert S\rvert\le 10^6$，字符串只含大写字母和 ?。