Polyominoes are 2-dimensional shapes, made of squares glued by edges. The name comes as an extension of domino
(referring to typical 1x2 rectangular shape of domino game pieces). It is easy to figure out there are
two types of trimino (made of 3 squares) and five types of tetramino (made of 4 squares) - not counting
rotations and mirror-variants of the same shapes:
trimino tetramino
--------- -------------------------------
XXX XX XXXX XXX XXX XX XX
X X X XX XX
They provide us with a number of curious puzzles - many of them about tiling some larger shape with given set of polyominoes. However the very first problem we encounter when dealing with them - is generating all possible pieces!
If you don't know how many pentaminoes (and perhaps, hexaminoes) exists, it may be amusing to figure this out using pencil-and-paper. However total grows fast with the size (or degree) of polyomino and there seem to be no known formula. Feel free to check Wikipedia to find more details... or calculate yourself :)
Looking at any polyomino shape we can conclude that any of its squares has no less than 1 and no more than 4
neighbors (counting only those sharing a side). So we can describe any of the shapes by 4 values, telling how
many squares in it have 4, 3, 2 or just 1 neighbor. We'll use dots to concatenate these values into
tuple-of-four.
For example, both triminoes shown above are described as 0.0.1.2 - they have one square with two neighbors and
two squares with single neighbor. Tetraminoes have 3 shapes fitting 0.0.2.2 description, and two more described
uniquely as 0.1.0.3 (T-shape) and 0.0.4.0 (square block).
Given several such descriptions you are to answer how many polyominoes fit them. We limit our curiosity to
shapes of up to 13 squares.
Input gives a total number of descriptions in the first line. Then descriptions themselves follow, one per line.
Answer should give counts of polyminoes fitting these shapes.
Example
input data:
3
0.0.1.2
0.0.4.0
0.1.1.3
answer:
2 1 3
P.S. if your solution includes generation of all possible shapes, feel free to boast at forum up to which degree you were able to calculate - and how many memory / time is spent.