34649번 - Brain Power 다국어

You are given a string $s$ consisting of lowercase English letters. Your task is to split $s$ into a sequence of non-empty substrings such that no two adjacent substrings in the sequence are anagrams of each other. (Two strings are considered anagrams if they contain the same characters with the same frequencies.) Among all such valid splits, you must maximize the number of substrings.

The first line of the input contains a single integer $T$, the number of test cases.

The following $T$ lines each describe a test case. Each line contains a single string $s$ consisting of lowercase English letters.

For each test case, print a single integer on a new line: the maximum possible number of substrings in a valid split.

• $1 \le T \le 10^5$
• $1 \le |s| \le 10^5$ for each test case.
• The total length of all strings $s$ over all test cases does not exceed $10^5$.