这是问题 B2 的简化版本。也许您应该在开始解决 B1 之前先阅读问题 B2。
Paul 和 Mary 最喜欢的字符串 $$$s$$$ 由拉丁字母的小写字母组成。他们想用两种颜色的粉笔来画它:红色和绿色。如果满足以下条件,我们可以将字符串的着色称为“美妙”:
1. 字符串的每个字母要么只用一种颜色(红色或绿色)绘制,要么不绘制;
2. 每两个涂成相同颜色的字母不同;
3. 红色字母的数量等于绿色字母的数量;
4.在满足前三个条件的字符串的所有颜色中,该颜色所绘制的字母数量最多。
例如考虑字符串 $$$s$$$ 等于“kzaaa”。图中显示了绳子的美妙色彩之一。
字符串“kzaaa”的美妙着色示例。
保罗和玛丽想自学如何找到美妙的绳子颜色。但他们还很年轻,所以他们需要提示。帮助他们找到 $$$k$$$ — 颜色美妙的红色(或绿色,这些数字相等)字母的数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例由一个非空字符串 $$$s$$$ 组成,该字符串由拉丁字母的小写字母组成。字符串中的字符数不超过 $$$50$$$。
输出
对于每个测试用例,输出一个单独的行,其中包含一个非负整数 $$$k$$$ — 将以美妙的颜色涂成红色的字母数量。
示例
输入 #1
5 kzaaa codeforces archive y xxxxxx
输出 #1
2 5 3 0 1
注意
第一个测试用例包含语句中的字符串。图中显示了其中一种美妙的色彩。包含 $$$3$$$ 或更多红色字母的着色并不美妙,因为绘制的符号总数将超过字符串的长度。
第二个测试用例中的字符串可以按如下方式绘制。让我们将字母“c”、“o”、“e”第一次出现的地方涂成红色,第二次出现的地方涂成绿色。让我们将字母“d”、“f”涂成红色,将“r”、“s”涂成绿色。因此每个字母都会被涂成红色或绿色,因此不存在比 $$$5$$$ 更好的答案。
第三个测试用例包含不同字母的字符串,因此您可以将任何字符集绘制为红色,只要该集的大小不超过字符串大小的一半并且是可能的最大值。
第四个测试用例包含一个不能涂成红色的字母,因为没有字母可以涂成绿色。
第五个测试用例包含一串相同的字母,因此无法将多个字母绘制为红色。