Snake
Boy Vasya the lesson of mathematics, instead of listening to the teacher, drawing numbers in a notebook in the cell. Do not just draw, but in a certain way. First, he put in a cage number 1. Then the right of it drew the number 2. Then the bottom of the number 2 wrote the number 3. He then moved to the cell to the right and continued engaging lesson on moving up the column, while the number in this column does not become higher than the highest number in the previous column. He then proceeded to the cage to the right and again continued the drawing of numbers starting with 7, but already down until it drew a number that turned out to be one cell below the lowest number in the previous column. And so on. Vasya not like numbers ending in zero, and let them in drawing snakes. First of his six-filled columns, we have copied from his notebooks and brought here in the picture. Since Vasya very curious, he very much wants to know what kind of numbers he will have to stand in the N-th column in the row, which is the number 1. The first 6 of those numbers in this row can be seen in the figure: 1, 2, 5, 8, 14, 19.
Write a program that helps Vasya.
Input
We introduce a single number N (1 ≤ N ≤ 10^6) – the column number.
Output
Output N-th line, where is the number 1.