By Fábio Dias Moreira Brazil
Set is a game of cards in which each card may have one, two or three figures. All figures in one given card are equal. Figures may be circles, squares or triangles. Each card, therefore, has two characteristics: the number of figures and the type of figure. A set is a group of three cards such that, for each characteristic (number and figure), either the three cards are equal or the three cards are different.
For example, in the figure below, (a) is a valid set, since all cards have the same figure type and all of them have a different number of figures. In the example (b), both the type of figures and the number of figures are different, making also a valid set. On the other hand, (c) is not a valid set, as the last two cards have the same figure, which is different from the figure in the first card.
The objective of the game is to form the largest number of sets with the cards that are on the table. Once a set is formed, the three cards are removed from the game.
When there are few cards on the table, it is easy to determine the largest number of sets that can be formed; however, when there are many cards on the table the number of combinations is too high. A friend wants to practice for the Set World Championship, and has asked you to write a program to calculate the largest number of sets that may be formed with a given group of cards.
The input contains several test cases. The first line of a test case contains an integer N (3 ≤ N ≤ 3 x 104), indicating the number of cards on the table. Each of the next N lines contains the description of one card.
The description of one card is given by two words, separated by one space. The first word is:
indicating the number of figures in the card. The second word is
indicating the type of figure in the card. The end of input is indicated by a line containing only one zero.
For each test case in the input, your program must print a single line, containing one integer, indicating the largest number of sets that can be formed with the given cards.
|Input Sample||Output Sample|