This problem was used in the following GFU competitions:
GFU 2024 D1 Q7
You are given W, a set of N words that are anagrams of each other. There are no duplicate letters in any word. A set of words S which is a subset of W is called “swap-free” if there is no way to turn a word x which is a member of S into another word y which is also a member of S by swapping only a single pair of (not necessarily adjacent) letters in x. Find the size of the largest swap-free set S chosen from the given set W.
The first input will contain a single integer t that indicates the number of test cases that follow. Each test case will begin with an integer N (1 <= N <= 500). Following that are N lines each with a single word. Every word contains only lowercase English letters and no duplicate letters. All N words are unique, have at least one letter, and every word is an anagram of every other word.
For each test case, print on a single line the size of the largest swap-free set.
Example Input:
3
6
abc
acb
cab
cba
bac
bca
11
alerts
alters
artels
estral
laster
ratels
salter
slater
staler
stelar
talers
6
ates
east
eats
etas
sate
teas
Example Output:
3
8
4