Хлопчик Вася на уроці математики, замість того, щоб слухати вчителя, малював числа у зошиті в клітинку. І не просто так малював, а певним способом. Спочатку він поставив у клітинку число 1. Потім праворуч від неї написав число 2. Потім знизу від числа 2 написав число 3. Потім перейшов на клітинку правіше і провжив захоплюючу справу рухаючись по стовбчику вверх, доки число у цьому стовбці не стало вище самого верхнього числа у попередньому стовбчику. Потім він перейшов на клітинку правіше і знову таки продовжив написання чисел, починаючи з 7, але тільки вже зверху вниз, доки не написав число, яке опинилось на одну клітинку нижче самого нижнього числа у попередньому стовбці. І так далі. Вася не любив числа, що закінчуються нулем, і пропускав їх при малюванні змійки. Перші його шість заповнених стовбців ми скопіювали з його зошита і навели тут на рисунку. Так як Вася дуже допитливий, то він дуже хоче взнати, яке ж число буде у нього стояти у N-ому стовбчику у тому рядку, де стоїть число 1. Перші 6 таких чисел у цьому рядку видні на рисунку: 1, 2, 5, 8, 14, 19.
Напишіть програму, яка поможе Васі.
Вводиться одне число N (1 ≤ N ≤ 10^6) – номер стовбця.
Вивести N-те число у рядку, де стоїть число 1.