
ZOJ Problem Set  3729
Do you know Vladimir Arnold? He's a mathematician who demonstrated an image transformation method called arnold transformation, which could shuffle all pixels in an image, and after a serials of this transformation, the image would be transformed to its original form. The transformation method is quite simple. For a given image with N × N pixels (Width and height are both equal to N), a pixel at location (x, y) will be shuffled to location ((x + y) % N, (x + 2 × y) % N) (0 ≤ x < N, 0 ≤ y < N). In one step of transformation, all N × N pixels will be shuffled to new corresponding location, making the image a chaotic one. You can do the transformation as many times as you can. The arnold transformation is very interesting. For every image of size N × N, after finite steps of transformation, the image will become exact the same as the original one. The minimum number of steps which make every possible image become the same as origin will be called as period of arnold transformation. For a given N, can you calculate the period? InputThere will be not more than 200 test cases. For each test case, there will be an integer N in one line. Here N (2 ≤ N ≤ 4000000000) equals to width and height of images. OutputFor each test case, please calculate the period of arnold transformation and output it in one line. Sample Input11 29 41 Sample Output5 7 20 Author: FAN, Yuzhe Contest: The 2013 ACMICPC Asia Changsha Regional Contest 