给你一个由小写英文字母组成的字符串 $s$。你的任务是将 $s$ 分割成一个非空子串序列，使得序列中任意两个相邻的子串互不为变位词（anagrams）。（如果两个字符串包含相同的字符且每个字符出现的次数也相同，则认为它们互为变位词。）

在所有合法的分割方案中，你必须最大化子串的数量。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

接下来的 $T$ 行，每行描述一个测试用例。每行包含一个由小写英文字母组成的字符串 $s$。

输出格式

对于每个测试用例，在新的一行中输出一个整数：表示合法分割中最多可以得到的子串数量。

数据范围

• $1 \le T \le 10^5$
• 每个测试用例中，$1 \le |s| \le 10^5$
• 所有测试用例中字符串 $s$ 的总长度不超过 $10^5$

样例

输入样例 1

5
kaist
rrunnn
iiccppcc
mooockk
connttest

输出样例 1

5
4
6
5
8

输入样例 2

8
a
bb
ccc
dddd
eeeee
ffffff
ggggggg
hhhhhhhh

输出样例 2

1
1
2
3
3
4
5
5

输入样例 3

4
brainpowerletthebasskick
oooooooooooaaaaeaaiau
joooooooooooooaaeoaauua
eeeeeeeeeaaaaeaeiea

输出样例 3

22
15
17
15