Everyone knows that Santa's Elves are non-gendered and reproduce by magic. Every time a new Elf is needed, two other Elves 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. Elves, too, never create other elves without magical powers.

Because it was so easy to create new Elves, 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 Elves 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 Elves 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 ≤ 10⁵) representing the number of Elves currently in the Santa factory. The following are N lines each containing a sequence of max. 64 characters C_i. C_i 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 distinct from uppercase letters.

Output

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

Example

Input:
3
2
xz
yx
3
xz
yx
zy
5
xazt
ctz
cax
xz
at

Output:
1
0
2