beecrowd | 2935

# DNA of Elf

By Francisco Elio Parente Arcos Filho, UEA Brazil

Timelimit: 1

Everyone knows that Santa's Elfs are non-gendered and reproduce by magic. Every time a new Elf is needed, two other Elfs come together, build a snowman, put a hair of each of them on him and then use their magical powers to give life to the snowman who becomes an Elf. This Elf always inherits the magical powers of its creators, unless both creators possess the same type of power, so the new Elf does not inherit such power because there is a magical overhead. Elfs, too, never create other elves without magical powers.

Because it was so easy to create new Elfs, Santa realized that his subordinates were creating many new helpers, not thinking about the consequences. Simply to lessen your workloads. So he decided to forbid the creation of new Elfs who already had the same set of powers as any existing Elf, as this would be redundant given that a single Elf with that set of powers is more than enough for the function that is designated. In addition there may already be more than one Elf of that type because it was created before Good Old Man vetoed the creations.

Now the little magical beings live a dilemma: Given the information of all types of powers that each Elf has, what is the maximum number of new Elfs that can still be created?

## Input

The first line of the entry contains an integer T corresponding to the number of test cases that follow. The first line of a test case contains an integer N (1 ≤ N ≤ 105) representing the number of Elfs currently in the Santa factory. The following are N lines each containing a sequence of max. 64 characters Ci. Ci is always a lowercase or uppercase letter of the English alphabet or a digit from 0 to 9 and represents a type of magic power. Lowercase letters represent types of magic power distint than uppercase letters.

## Output

The output consists of one line per test case containing the maximum number of Elfs that can still be created without contradicting Santa's ban.

 Input Sample Output Sample 3 2 xz yx 3 xz yx zy 5 xazt ctz cax xz at 1 0 2