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 low- ercase letters where each letter repre- sents a different base. Note that hu- man DNA is also a sequence of base sets, except a base set is simply a pair- ing of a with t or c with g. Since alien DNA is more compli- cated than human DNA, the algo- rithms used in alien bioinformatics are also much more complicated. How- ever, 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 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. Output For each test case, output the minimum number of cuts required to partition the strand into segments that share a common base. Sample Input 2 5 as sd df fg gh 3 Unfortunately, this is not a Magic Eye
2/2 plum orange plum Sample Output 2 2