已知有$n$位同学，其中$n$是大于或等于$1$的正整数，他们之间等距离的站成一个圆形，如图所示。按照顺时针方向分别给每位同学一个编号，编号从$1$开始，依次为$2，3，4,\cdots n-1,n$。其中，编号为$1$的同学必须站在如图所示的圆的正上方向。

假设有$4$位同学的话，则所站位置如图所示：

下面从第一位同学开始，按顺时针方向，依次进行报数，当某位同学所报数数目为$3$的倍数时，则该同学退出该圆，于是按顺时针方向，后面的同学接着进行报数，比如当某位同学报到了$9$，则他退出，他后面一位同学从$10$开始继续报数，依此类推。比如，当在圆上只有一位同学时，则他的序号为$1$，从他开始报数，第一次报$1$，不是$3$的倍数，于是第二次接着报，他报$2$，也不是$3$的倍数，第三次又是他报，他报$3$，此时，$3$是$3$的倍数，则他是最后一个离开该圆的同学。

又比如，当圆上站着两个同学的时候，则第一个同学报$1$，第二个同学报$2$，因为只有两个同学，于是又轮到第一个同学报了，此时他该报$3$，则他退出该圆；剩下第二位同学，再按此规则进行，则最后一个离开该圆的同学肯定就是编号为$2$的同学了。

请你编程，求整数$n$给定后，按上述游戏规则进行报数时，最后一个离开该圆的同学的编号。

输入格式

输入只包含一行，其内容是一个整数，即人数$n$的值  $n\leq 1000$

输出格式

输出也仅含一行，其内容也是一个整数，即最后一个离开该圆的同学的编号。

样例

样例输入

1

样例输出

1

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$262144\mathrm{KB}$