Problem B. Boustrophedon

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  


Boustrophedon is a type of bi-directional text, mostly seen in ancient manuscripts and other inscriptions.

Every other line of writing is reversed. Rather than going left-to-right as in modern English, alternate lines in boustrophedon must be read in opposite directions. The individual character images on reversed lines are mirrored too.

Notice that some Latin letters are symmetrical, and so do not need mirroring on the reversed lines. This way, some English texts may be written as boustrophedons with the standard font. The symmetrical letters are: A, H, I, M, O, T, U, V, W, X, Y.

The boustrophedon must consist of at least 3 lines. All lines of the boustrophedon must have the same number of characters (let us call it the width of the boustrophedon), except the last line, which may be shorter. The text contains only capital English letters (no spacing or punctuation).

You program must find the width of the widest boustrophedon that can be constructed from the given text and does not need letter mirroring.

Input file format

Input file contains a single string composed of capital Latin letters.

Output file format

Output file must contain a single integer — maximum boustrophedon width. If there is no solution, output zero.


String length is between 1 and 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)

0.186s 0.021s 15