| Set |
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 description of one card is given by two words, separated by one space. The first word is:
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.
3 um circulo dois circulos tres circulos 3 um triangulo tres quadrados dois circulos 6 dois quadrados dois quadrados dois quadrados dois quadrados dois quadrados dois quadrados 4 um quadrado tres triangulos um quadrado dois triangulos 0
1 1 2 0