# 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

• 写回答

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

• threenewbee 2017-09-12 16:46
关注
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 OpenFOAM多孔介质传热模型建模
• ¥15 QT 实现 RSTP 语音对讲功能
• ¥50 AES魔改之后的安全性关于PRF（相关搜索：密码学）
• ¥15 用C语言写的一个程序遇到了两个问题第一是偏移正确但读取不到坐标，第二个问题是自己定义的函数实现不了获取指定进程模块。
• ¥15 在安装Anaconda时总是闪退怎么办?
• ¥15 对图中电路进行以下几个方面的分析
• ¥15 对图中电路进行以下几个方面的分析
• ¥15 对图中电路进行以下几个方面的分析
• ¥15 对图中电路进行以下几个方面的分析
• ¥500 抖音主页视频预存加载卡bug