Minimum Operations to Reach an Integer

Given a nonnegative integer \( k \), define a real number \( r = k + \frac{1}{2} \). An operation on \( r \) is defined as follows:

\[ r \leftarrow r \times \lceil r \rceil, \] where \( \lceil r \rceil \) is the smallest integer not less than \( r \). The task is to determine the minimum number of operations required to make \( r \) an integer. If it is impossible to obtain an integer value of \( r \) using these operations, output \(-1\).

Note: For any positive integer \( k \), when \( r = k + \frac{1}{2} \), one can show that:

• If \( k \) is odd, one operation is sufficient.
• If \( k \) is even and positive, two operations are required.

However, when \( k = 0 \), the value of \( r \) is \( \frac{1}{2} \), and the operation does not change \( r \) (since \( \lceil \frac{1}{2} \rceil = 1 \)), making it impossible to ever reach an integer.

inputFormat

The input consists of a single nonnegative integer \( k \) (\( 0 \leq k \leq 10^9 \)).

outputFormat

Output a single integer which is the minimum number of operations required to make \( r = k + \frac{1}{2} \) become an integer. If it is impossible, output \(-1\).

sample

0

-1