Square Remainder Count

Given a positive integer \(n\) (with \(n \ge 2\)), consider all positive integers \(v\) such that \(1 \le v < n\). For each \(v\), compute the remainder when \(v^2\) is divided by \(n\), i.e. \(v^2 \bmod n\). Count the number of \(v\) for which the remainder is less than \(\frac{n}{2}\).

In other words, find the number of integers \(v\) (\(1 \le v < n\)) for which the following inequality holds: \[ v^2 \bmod n < \frac{n}{2}. \]

For example, when \(n = 4\):

• \(1^2 \bmod 4 = 1\) which is less than \(2 = \frac{4}{2}\),
• \(2^2 \bmod 4 = 0\) which is less than \(2\),
• \(3^2 \bmod 4 = 1\) which is less than \(2\).

So the answer is 3.

As another example, when \(n = 5\):

• \(1^2 \bmod 5 = 1\) which is less than \(2.5 = \frac{5}{2}\),
• \(2^2 \bmod 5 = 4\) which is not less than \(2.5\),
• \(3^2 \bmod 5 = 4\) which is not less than \(2.5\),
• \(4^2 \bmod 5 = 1\) which is less than \(2.5\).

So the answer is 2.

inputFormat

The input consists of a single integer \(n\) (\(n \ge 2\)).

outputFormat

Output a single integer representing the count of numbers \(v\) (with \(1 \le v < n\)) satisfying \(v^2 \bmod n < \frac{n}{2}\).

sample

4

3