题目描述

给你 2N 张牌，编号为 1 , 2 , 3 , ..., n , n+1 , ... , 2n 。这也是最初的牌的顺序。

一次洗牌是把序列变为 n+1 , 1 , n+2 , 2 , n+3 , 3 , n+4 , 4 , ... , 2n , n 。

可以证明，对于任意自然数N，都可以在经过M次洗牌后第一次重新得到初始的顺序。

编程对于小于 10000 的自然数 N ，求出 M 的值。

输入格式

一个自然数 N 。

输出格式

洗牌次数 M 。

样例

20

20