The Turn of the Shrew

Dr. Montgomery Moreau has spent many years observing a wild population of Northern Madagascar Pied Shrews. He has carefully catalogued every shrew in the area, recording its distinctive physical characteristics and giving each animal a name.

He keeps a list of significant physical characteristics (for example: brown fur, red eyes, white feet, prominent incisor teeth). For each characteristic he has recorded whether it is dominant: if either parent has a dominant characteristic, the child has it too.

Recently he has come to suspect that the population is undergoing a high rate of genetic mutation (perhaps because of the strange glowing rock near their communal burrow). When the shrews emerged from the burrow at the end of last winter, he noticed several youngsters whose characteristics did not match any possible pair of parents.

For each juvenile shrew, determine the smallest number of mutations that could account for its parentage.

The input contains one or more data sets.

Each data set is a sequence of lines, one per animal. Every line starts with a single character, M, F, or C, denoting a male adult, a female adult, or a child, respectively. Each data set contains at least one line of each type. The initial character is followed by a single blank and then by a genetic code of 1 to 40 consecutive 0 and 1 characters. Within one data set, every genetic code has the same length.

In a genetic code, a 1 means the animal has the physical characteristic controlled by that dominant gene and a 0 means it does not. A data set ends with a line whose first character is X. The end of all input is marked by a second, consecutive line whose first character is X.

Ignoring mutation, a child may have a 1 at a position only if at least one parent has a 1 there, and may have a 0 at a position only if both parents have a 0 there. (Equivalently, without mutation the child's code equals the bitwise OR of its two parents' codes.) A pair of parents always consists of one male adult and one female adult. Each mutation changes exactly one position of the code.

For each child, in the order the children appear in the input, print one line:

Child K has a minimum of N mutations.

Here K is the child's index, starting at 1 and increasing by one with every output line, and N is the minimum number of mutations that could account for this child being born to some pair of adults.