Các số tự nhiên từ ~1~ đến ~N~ được xếp trên một vòng tròn theo chiều kim đồng hồ. Bắt đầu từ số ~1~, cứ bước qua một số thì xóa số ngay trước nó. Quá trình tiếp tục cho đến khi chỉ còn lại một số.

Yêu cầu: Tìm số còn lại cuối cùng.

Input

Đọc từ file văn bản XOASO.INP một số nguyên ~N~ ~(1 \le N \le 3000)~.

Output

Ghi ra file văn bản XOASO.OUT một số nguyên là số còn lại.

Example input 1

10

Example output 1

5