Shuffling the pixels in a bitmap image sometimes yields random looking images. However, by repeating the shuffling enough times, one finally recovers the original images. This should be no surprise, since "shuffling" means applying a one-to-one mapping (or permutation) over the cells of the image, which come in finite number.

Your program should read a number n , and a series of elementary transformations that define a "shuffling" of n * n images. Then, your program should compute the minimal number m (m > 0) , such that m applications of always yield the original n * n image.

For instance if is counter-clockwise 90^o rotation then m = 4.

Input

Test cases are given one after another, and a single 0 denotes the end of the input. For each test case:

Input is made of two lines, the first line is number n (2 <= n <= 2¹⁰ , n even). The number n is the size of images, one image is represented internally by a n * n pixel matrix (a^j_i) , where i is the row number and j is the column number. The pixel at the upper left corner is at row 0 and column 0.

The second line is a non-empty list of at most 32 words, separated by spaces. Valid words are the keywords id, rot, sym, bhsym, bvsym, div and mix, or a keyword followed by -. Each keyword key designates an elementary transform (as defined by Figure 1), and key- designates the inverse of transform key. For instance, rot- is the inverse of counter-clockwise 90^o rotation, that is clockwise 90^o rotation. Finally, the list k₁, k₂, ..., k_p designates the compound transform = k₁ok₂o ... ok_p . For instance, "bvsym rot-" is the transform that first performs clockwise 90o rotation and then vertical symmetry on the lower half of the image.

Figure 1: Transformations of image (a^j_i) into image (b^j_i)

Output

For each test case:

Your program should output a single line whose contents is the minimal number m (m > 0) such that is the identity. You may assume that, for all test input, you have m < 2³¹.

Example

Input:
256
rot- div rot div
256
bvsym div mix
0
Output:
8
63457