Телепортацiя

До чого дійшов прогрес! Роботи зі штучним інтелектом намагаються опанувати телепортацію!

Відбувається це так. Є ряд з кубічних боксів, пронумерованих числами від 1 до $N$. Робот Аліса знаходиться в боксі з номером 1, а робот Боб $-$ в боксі з номером $N$. Щосекунди Аліса телепортується у бік Боба, а Боб $-$ у бік Аліси. Якщо Аліса знаходиться в боксі з номером $k$, то через секунду вона може телепортуватися в бокс з номером $k+2$ або в бокс з номером $k+3$. Якщо ж Боб знаходиться в клітинці з номером $k$, то через секунду він може телепортуватися в бокс з номером $k-1$ або в бокс з номером $k-2$. Телепортація можлива, якщо бокс, в який відбувається телепортація існує.

За процесом телепортації уважно спостерігає робот Єва. Вона дуже хвилюється за стан здоров'я Аліси та Боба, тому її цікавить два питання: чи можуть Аліса та Боб опинитися в одному боксі і яка мінімальна кількість секунд на це потрібна. Допоможіть Єві це з'ясувати!

Input

Ваша програма отримує на вхід одне ціле число $N$ $-$ кількість боксів для експерименту з телепортацією.

$2\le N\le 1000000000$

Output

Якщо Аліса та Боб зможуть опинитися в одному боксі, то виведіть мінімальну кількість секунд, необхідних для цього. Якщо Аліса та Боб не зможуть опинитися в одному боксі, то виведіть число «-1».

Examples

Note

У першому прикладі Аліса може телепортуватися з боксу номер 1 або в бокс з номером 3, або в бокс з номером 4. А Боб може телепортуватися з боксу з номером 5 в бокс з номером 4 або в бокс з номером 3. Таким чином, через одну секунду Аліса та та Боб зможуть зустрітися в боксі з номером 3 або в боксі з номером 4.

У другому прикладі Аліса та Боб зможуть опинитися в одному боксі через 2 секунди. Наприклад, Аліса спочатку телепортується в бокс з номером 3, а потім в бокс з номером 6, Боб телепортується спочатку в бокс з номером 8, а потім в бокс з номером 6.