题目描述

给你 $2N$ 张牌，编号为 $1, 2, 3, \ldots, n, n+1, \ldots, 2n$，这也是最初的牌的顺序。一次洗牌是把序列变为 $n+1, 1, n+2, 2, n+3, 3, n+4, 4, \ldots, 2n, n$。可以证明，对于任意自然数 $N$，都可以在经过 $M$ 次洗牌后第一次重新得到初始的顺序。编程对于小于 $10000$ 的自然数 $N$，求出 $M$ 的值。

输入格式

一个自然数 $N$。

输出格式

洗牌次数 $M$。

样例

20

20

数据范围

• $1 \le N < 10000$