洗牌问题

题目描述

有 $ 2n $ 张牌,编号为 $$ 1,2,3 \dots n,n+1, \dots 2n$$ 这也是最初的牌的顺序。一次洗牌是把序列变为 $$ n+1,1,n+2,2,n+3,3,n+4,4 \dots 2n,n $$ 可以证明,对于任意自然数 $ n $,都可以在经过 $ m $ 次洗牌后第一次重新得到初始的顺序。 现给定 $n$($n \le 10^8$),求出 $ m $ 的值。

输入输出格式

输入格式


一行,一个正整数 $n$。

输出格式


一行,一个正整数 $m$。

输入输出样例

输入样例 #1

20

输出样例 #1

20

说明

对于 $100 \%$ 的数据,$1 \le n \le 10^8$。