Alien DNA is more complicated than human DNA. For example, rather than
viewing an alien DNA strand as a sequence of base pairs, it can be viewed as a sequence
of base sets. A base set is, simply put, a string of lowercase letters where
each letter represents a different base. Note that human
DNA is also a sequence of base sets, except a base set is simply a pairing of a
with t or c with g.
Since alien DNA is more complicated than human DNA, the algorithms used in alien bioinformatics are also much more complicated. However, you have only been working at AlienBioTechNextGenCorp for three days and are not yet trusted enough to handle the complicated tasks.
Your first job is simple. You must develop software to cut a strand of alien DNA into as few segments as possible. The only constraint is that base sets of a given segment must share at least one common base.
Input begins with an integer t ≤ 100, the number of test cases to be processed. Each test case begins with a single value n (1 ≤ n ≤ 10,000) representing the length of the alien DNA strand. Each of the n following lines consists of a single string of lowercase letters representing a base set. Each string will contain at least one character, and no repeated characters. The base sets are given in the input in the same order they appear on the DNA strand.
For each test case, output the minimum number of cuts required to partition the strand into segments that share a common base.
2 5 as sd df fg gh 3 plum orange plum
2 2