Trên bàn có một dãy các ô, các ô đánh số liên tiếp bắt đầu từ ~1~, từ trái sang phải. An có một bộ bài gồm ~n~ lá bài có số hiệu là ~1, 2, 3, \dots, n~. Để chọn ra lá bài may mắn bạn An thực hiện các thao tác như sau:

Bước 1: An chia các lá bài hiện có vào các ô liên tiếp bắt đầu từ ô thứ nhất với số hiệu các lá bài theo thứ tự tăng dần.

Bước 2: An nhặt các lá bài trong các ô có số thứ tự chia cho ~3~ dư ~2~ và loại bỏ các lá bài còn lại trên dãy. Nếu số lá bài nhặt được nhiều hơn ~1~ thì quay lại thực hiện Bước 1. Trong trường hợp nhặt được đúng ~1~ lá thì lá bài đó là lá bài may mắn.

Ví dụ: Với ~n = 15~:

• Lần thứ nhất An sẽ chia các lá bài: ~1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15~ Nhặt các lá bài ~2, 5, 8, 11, 14~.
• Lần thứ hai An sẽ chia các lá bài: ~2, 5, 8, 11, 14~ Nhặt các lá bài ~5, 14~.
• Lần thứ ba An sẽ chia các lá bài: ~5, 14~ Nhặt lá bài ~14~ là lá bài may mắn.

Yêu cầu: Cho biết ~n~, hãy tìm ra số hiệu của lá bài may mắn.

Input

• Gồm một số nguyên dương ~n~ (~2 \le n \le 10^9~).

Output

• Ghi ra một số nguyên dương duy nhất là số hiệu của lá bài may mắn.

Sample Input 1

15

Sample Output 1

14