Monopoly
In the current business world there are many situations of participation
of a company in the capital of another, of cross-participations and of partnerships.
The amount of capital owned by each participant determines the number of votes. An entity
possessing 50%+1 votes controls the company. This entity may be a single company or a
partnership of several companies. To make the process more complex, a company may control
another indirectly, because if company A controls company B, and B controls C, then A
controls C. Thus it is not always clear who controls what.
In order to understand the power relationships among companies, a knowledgeable stock
exchange broker writes down some facts of the form A > B, meaning company A controls company B.
He also writes more generic facts like A1 … An > B meaning that a
possible partnership ofcompanies A1 … An is able to control B. Due to
the empiric process used, the set of facts may include many redundancies, of two types:
Type 1: if A B C > D is a fact but it can be concluded from the set of facts
that A and B together are enough to control D (directly or indirectly), then C can be
deleted from the former fact because it is irrelevant.
Type 2: if there is a fact A > B but it can be concluded just from the other
facts that A controls B, then A > B may be deleted because it is redundant.
To get a clearer picture of the essential relationships, an analyst would
like to have a minimal version of the set of facts without redundancies, but also without
loosing information. There may be several alternative minimal sets of facts.
Given an initial set of facts of the form A1 … An > B a minimal set is an equivalent set that contains neither redundancies of type 1 nor of type 2. Which is the number of facts of the smallest minimal set?
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of the input contains the integer number N of facts. Each of the following N lines contains a string of k (1<= k <= 26) capital letters, the symbol > and a single capital letter. Each capital letter represents a company.
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
One line containing the number of facts of the smallest minimal set.
Sample Input
1
11
AB>C
C>A
BC>D
ACD>B
D>E
D>G
BE>C
CG>B
CG>D
CE>A
CE>G
Sample Output
8