Genetics

A colony of alien bacteria has recently been discovered near a crater in New Mexico. Dr. Poucher leads the scientific team at the ICPC BioLab devoted to studying the structure of the alien DNA. Their discoveries are sketched briefly below.

An alien DNA molecule has the structure of a circular sequence composed of nucleotides. There are 26 different types of nucleotides, and each of them can occur in two faces. Crucially, in any given alien DNA molecule every nucleotide either does not appear at all or appears exactly twice (so the length of a molecule is an even integer between 2 and 52). When a nucleotide occurs twice, each occurrence may independently take either face. Alien bacteria have two kinds of extremities, called arms and legs in the technical jargon. A major discovery of Dr. Poucher's team is a method to determine the exact number of arms and legs of a bacterium from its DNA structure.

We represent each nucleotide by a letter of the alphabet. We write the nucleotides as $a, A, \dots, z, Z$, where the lowercase and uppercase forms of a letter denote the two possible faces of a nucleotide; we also write $a/A, b/B, \dots, z/Z$ to refer to a nucleotide in either face.

To determine the number of extremities, Dr. Poucher initializes two counters (arms and legs) to zero and performs a series of surgeries, each transforming the sequence into another one. After a transformation you may have to increase one of the counters, depending on the surgery applied. When the empty sequence (denoted $\emptyset$) is reached, the number of extremities of the original molecule has been found. The possible surgeries are:

1. Eliminate two consecutive occurrences of a single nucleotide that appear with opposite faces. The numbers of arms and legs are preserved. For example, aBbCaC becomes aCaC by eliminating Bb, and DeHhEd becomes eHhE by eliminating dD. Remember that the DNA is circular, so in the string representation the last and first letters are adjacent.
2. Eliminate two consecutive occurrences of a single nucleotide that appear with the same face. Add one to the number of arms. For example, BBcgCg becomes cgCg by eliminating BB, and xabyyaBX becomes xabaBX by eliminating yy.
3. Eliminate four nucleotides made of two different nucleotides appearing alternately, where the two occurrences of each nucleotide have opposite faces. Add one to the number of legs. For example, dcDCefFe becomes efFe by eliminating dcDC, and cmNMnC becomes cC by eliminating mNMn.
4. Cut and paste, the most elaborate procedure. First, choose a nucleotide, say $a/A$, and chop the circular sequence into two linear chains so that the nucleotide appears once in each of them. Second, if both occurrences of $a/A$ have the same face, invert one of the chains by reversing it and flipping the face of every nucleotide in it. Then combine the chains by concatenating the part before $a$ with the part after $A$, and the part after $a$ with the part before $A$. Finally, add two new $a/A$ nucleotides to close the chain into a circle; the two new nucleotides have the same face if the original pair had the same face, and different faces otherwise. Formally, if $a/A$ appears both times with face $a$ (or both times with face $A$), the surgery turns a sequence $S_1 a S_2 S_3 a S_4$ (respectively $S_1 A S_2 S_3 A S_4$) into $S_2 a S_1 \bar{S}_3 a \bar{S}_4$ (respectively $S_2 A S_1 \bar{S}_3 A \bar{S}_4$), where $\bar{S}$ denotes the inverted chain. If instead $a/A$ appears with its two different faces, the surgery turns $S_1 a S_2 S_3 A S_4$ into $S_2 a S_1 S_4 A S_3$. Here $S_1, S_2, S_3, S_4$ are arbitrary (possibly empty) sub-chains, and the original circle was chopped into $S_1 (a/A) S_2$ and $S_3 (a/A) S_4$. For example, starting from BacDcAbD we can cut out the chains BacDc and AbD; merging at $a/A$ gives cDcaBbDA, where the final a and A are the two new nucleotides, with $S_1 =$ B, $S_2 =$ cDc, $S_3 = \emptyset$, $S_4 =$ bD. As another example, cutting the same BacDcAbD into DBac and DcAb and pasting at $c/C$ (here one chain must be inverted, e.g. BaCd) gives cDBadcBa, with $S_1 =$ DBa, $S_2 = \emptyset$, $S_3 =$ D, $S_4 =$ Ab. This surgery changes neither the arms nor the legs, but can be used together with the previous surgeries to shrink the molecule and finish the computation.

However, alien bacteria never have arms and legs at the same time: early in their development, a leg turns into two arms whenever at least one arm is present. Consequently the final result is a number of arms or a number of legs, but never both. To avoid costly surgery, Dr. Poucher has hired you to write a program that, given a DNA sequence, computes the number of arms and legs the bacterium will develop. The result is guaranteed to be uniquely determined by the original string, independently of the particular sequence of surgeries applied.

Each test case is a string of even length between 2 and 52 inclusive, representing the DNA structure of an alien bacterium; all characters are letters. There is one case per line. The last line contains the word END and must not be processed.

For each test case, print exactly one line containing the number of arms or legs the bacterium will have, followed by the word arms or legs respectively (use the singular arm or leg when the number is 1). If there are neither arms nor legs, print none.