Migrated from Lutece 705 Draw Bones

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Miss Cat wants to draw a picture as a present for Mr.Dog's birthday. Knowing bones are dog's favorite, Miss Cat decides to draw some bones. Since it's Mr.Dog's $N_{th}$ birthday, $N$ identical bones are needed. To complete this task, Miss Cat can do one of the four following operations every time.

1. Draw: draw a single bone.
2. Delete: delete a single bone that has already existed.
3. Copy: copy all the existing bones to the clipboard.
4. Paste: paste clipboard contents to current picture.

Please note that the content in clipboard changes only after you perform a copy operation. In the beginning, both the picture and the clipboard are empty.

Now, Miss Cat wants to complete the picture as soon as possible. Please help her to calculate how many operations she needs at least.

Input

Input file consists of multiple test cases, ended by EOF. Every case contains only one integer $N$ ($0 < N\leq 2000$).The number of test cases will not exceed $2000$.

Output

Output one line containing the answer for every case.

Samples

2
4
6

2
4
5

Resources

The 7th BUPT Collegiate Programming Contest