暂无测试数据。

Description

给你 \(2\cdot n\) 张牌，编号为 \(1,2,3,\cdots,n,n+1,n+2,\cdots,2n\)。这也是最初的牌的顺序。
一次洗牌是把序列变为 \(n+1,1,n+2,2,n+3,3,n+4,4,\cdots,2n,n\)。
可以证明，对于任意自然数 \(n\)，都可以在经过 \(m\) 次洗牌后第一次重新得到初始的顺序。
例如：对于 \(n=3\) 时
初始状态：\(1 \ 2 \ 3 \ 4 \ 5 \ 6\)
Step1：\(4 \ 1 \ 5 \ 2 \ 6 \ 3\)
Step2：\(2 \ 4 \ 6 \ 1 \ 3 \ 5\)
Step3：\(1 \ 2 \ 3 \ 4 \ 5 \ 6\)
编程对于自然数 \(n\)，求出 \(m\) 的值。

---

Input

一个整数 \(n\)，就是牌的一半的数量。

---

Output

一个整数 \(m\)，表示经过 \(m\) 次洗牌，且 \(m\) 是所能满足条件的最小值。

---

Sample

Sample input

3

Sample Output

3

Hint

对于 \(70\%\) 的数据满足 \(m\le 3000\)；
对于 \(100\%\) 的数据满足 \(n\le 10000\)，\(m\le 20000\)。