# Arnold

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?

Input

There 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.

Output

For each test case, please calculate the period of arnold transformation and output it in one line.

Sample Input

11
29
41
Sample Output

5
7
20

• 写回答

#### 2条回答默认 最新

• threenewbee 2017-04-21 13:57
关注
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 这个四人抢答器代码哪儿有问题？仿真程序怎么写？
• ¥15 burpsuite密码爆破
• ¥15 关于#ubuntu#的问题，如何解决？（相关搜索：移动硬盘）
• ¥15 scikit安装之后import不了
• ¥15 Ros2编译一个使用opencv的c++节点的时候，报了这个错误，请问怎么解决啊
• ¥15 人脸识别相关算法 YOLO，AI等
• ¥15 spark问题方便加V17675797079
• ¥15 Python代码不打印的原因
• ¥20 微软SEAL库的安装和使用，VS2022环境配置问题
• ¥15 数学问题也不知道那种类型的问题