Shuffling the pixels in a bitmap image sometimes yields ran- dom 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 el- ementary transformations that define a “shuffling” φ of n × n images. Then, your program should compute the minimal num- ber m (m > 0), such that m applications of φ always yield the original n × n image. For instance if φ is counter-clockwise 90o rotation then m = 4. Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. Input is made of two lines, the first line is number n (2 ≤ n ≤ 210, n even). The number n is the size of images, one image is represented internally by a n × n pixel matrix (aji ), 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 90o rotation, that is clockwise 90o rotation. Finally, the list k1, k2, . . . , kp designates the compound transform φ = k1 ◦ k2 ◦ · · · ◦ kp. For instance, “bvsym rot-” is the transform that first performs clockwise 90o rotation and then vertical symmetry on the lower half of the image.
2/3 id , identity. Nothing changes : bji = aji . rot , counter-clockwise 90o rotation sym , horizontal symmetry : bj = an−1−j ii bhsym , horizontal symmetry applied to the lower half of image : when i ≥ n/2, then bj = an−1−j. Otherwise bj = aj. ii ii bvsym , vertical symmetry applied to the lower half of image (i ≥ n/2) div , division. Rows 0,2,...,n − 2 become rows 0,1,...n/2 − 1, while rows 1,3,...n−1 become rows n/2,n/2+1,...n−1. mix , row mix. Rows 2k and 2k + 1 are interleaved. The pixels of row 2k in the new image are a0 ,a0 ,a1 ,a1 ,···an/2−1,an/2−1, 2k 2k+1 2k 2k+1 2k 2k+1 while the pixels of row 2k + 1 in the new image are an/2, an/2 , an/2+1, an/2+1, · · · , an−1, an−1 . 2k 2k+1 2k 2k+1 2k 2k+1 Figure 1: Transformations of image (aji ) into image (bji ) Output For each test case, your program should output a single line whose contents is the minimal number m (m > 0) such that φm is the identity. You may assume that, for all test input, you have m < 231. The outputs of two consecutive cases will be separated by a blank line. Sample Input 2 256 rot- div rot div 256 bvsym div mix
3/3 Sample Output 8 63457