На заводі кожна з ~N~ деталей може бути обробленою на одному з двох верстатів: ~A~ або ~B~. Кожна деталь має порядковий номер від 1 до ~N~. До обробки деталі приступають послідовно, у відповідності з номерами. Кількість деталей завжди парна. Існують правила, за якими визначається, чи можна обробляти деталь на певному верстаті.

1) Якщо на поточний момент на верстаті ~B~ була оброблена така ж кількість деталей, як і на верстаті ~A~, то наступна деталь повинна бути оброблена на верстаті ~A~.

2) У підсумку на кожному з верстатів повинно бути оброблено однакову кількість деталей.

Скільки існує людей, стільки й думок. Кожен із працівників цього заводу запропонував свою послідовність обробки деталей, причому всі пропозиції виявилися різними, але такими, що задовольняють правилам 1 і 2.

Напишіть програму, що за інформацією про кількість деталей ~N~ визначає максимальну можливу кількість працівників заводу.

Input

Єдиний рядок вхідного файлу містить парне число ~N~ (~2 \le N \le 28)~ – кількість деталей, які необхідно обробити.

Output

Єдиний рядок вихідного файлу має містити ціле число – максимальну можливу кількість працівників заводу.

Sample Input 1

4

Sample Output 1

2

Notes

Перший працівник вважає, що на верстаті ~A~ необхідно обробити деталі 1 та 2, а на верстаті ~B~, відповідно, 3 та 4. Другий має думку, що на верстаті ~A~ потрібно обробити деталі 1 та 3, а на B – деталі 2 та

1. Інших варіантів послідовності обробки деталей не існує.