该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

经典约瑟夫问题

Description

Zerg包围了你的城市，并准备对在此举行祭旗仪式。仪式是这样举行的：n个祭品（就是人类）编号1...n，排成一 圈，从1号开始，每隔一个，便将一个祭品送进Spawning Pool（就是把人变成虫子的地方啦），直到最后剩下一个 人，Zerg会把他放掉。Zerg认为这样做会给他们的战争带来好运。现在，没有丝毫反抗能力的你为了活命，必须站 在那个最后被剩下的位置。幸好你手中有一台电脑，它可以帮你迅速决定站在哪里。

Format

Input

每行一个正整数n(1<=n<=30000)，表示n个人被抓来祭旗

Output

输出一个正整数，表示应该站在哪个位置能生还。

Samples

100 

73

Limitation

1s, 1024KiB for each test case.