Problem Description

Xiaolan found that, for a positive integer $n$ and a positive integer $v$ less than $n$, after squaring $v$ and taking it modulo $n$, the result may be less than half of $n$, or it may be greater than or equal to half of $n$.

Ask: among the integers from $1$ to $n-1$, how many numbers have a remainder less than half of $n$ when their squares are divided by $n$.

For example, when $n=4$, the remainders of $1^2, 2^2, 3^2$ divided by $4$ are all less than half of $4$.

Another example: when $n=5$, the remainders of $1^2$ and $4^2$ divided by $5$ are both $1$, which is less than half of $5$. But the remainders of $2^2$ and $3^2$ divided by $5$ are both $4$, which is greater than or equal to half of $5$.

Input Format

The input contains one line with an integer $n$.

Output Format

Output one integer, the number of integers that satisfy the condition.

5

2

Hint

For all test cases, $1 \leq n \leq 10000$.

Lanqiao Cup 2021 Round 2 Provincial Contest, Group A Problem F (Group B Problem G).

Translated by ChatGPT 5