#68Easy

Power of two

Time: 1 s · Memory: 256 MB

Statement

You are given a natural number $n$ . If $n = 2^k$ , print $k$ , otherwise print $-1$ .

A single integer $n$ ( $1 \le n \le 10^{18}$ ).

A single integer — $k$ or $-1$ .

Input

Output

Input

Output

-1

While $n$ is even, divide it by $2$ and count the divisions. If $1$ is left at the end, $n$ is a power of two. $1 = 2^0$ , so the answer is $0$ .

Numbers up to $10^{18}$ need long long in C++ and int64 in Go.

Power of two

Time: 1 s · Memory: 256 MB

Working with numbers

You are given a natural number $n$ . If $n = 2^k$ , print $k$ , otherwise print $-1$ .

A single integer $n$ ( $1 \le n \le 10^{18}$ ).

A single integer — $k$ or $-1$ .

Input

Output

Input

Output

-1

While $n$ is even, divide it by $2$ and count the divisions. If $1$ is left at the end, $n$ is a power of two. $1 = 2^0$ , so the answer is $0$ .

Numbers up to $10^{18}$ need long long in C++ and int64 in Go.