Ta có thể chia một đa giác đều \(P\) gồm \(n\) cạnh thành tối đa \(n-2\) tam giác bằng cách nối một số đường chéo không giao nhau của \(P\). Ví dụ, một hình vuông có thể được chia thành hai hình tam giác và một hình ngũ giác đều có thể được chia thành ba hình tam giác. Ta gọi mỗi cách chia này là một cách tam giác phân của \(P\). Nếu \(n > 3\) thì \(P\) sẽ tồn tại ít nhất hai cách tam giác phân.

Ta định nghĩa khoảng cách giữa hai tam giác trong một cách tam giác phân của \(P\) chính là số cạnh mà ta phải băng qua để từ tam giác này đến được tam giác kia (không được đi ra khỏi \(P\)). Ví dụ, khoảng cách giữa tam giác \(a\) và tam giác \(d\) trong cách tam giác phân ở hình dưới là \(3\).

Ta tiếp tục quy ước đường kính của một cách tam giác phân của \(P\) chính là khoảng cách giữa hai tam giác xa nhất trong \(P\) theo cách tam giác phân đó. Cho biết \(n\) là số lượng cạnh của đa giác đều \(P\), bạn hãy lập trình tính toán đường kính nhỏ nhất có thể trong số các cách tam giác phân của \(P\) nhé!

Input

• Số nguyên dương \(n\) (\(3\leq n\leq 10^6\)).

Output

• Một số nguyên là đường kính nhỏ nhất tìm được.

Example

3

0

4

1

6

2