A positive integer is called binary palindromic if its binary representation (without leading zeros) reads the same from left to right and right to left.

You are given an integer N. In a single operation, you may perform one of the following:

• Increase the value of N by 1.
• Decrease the value of N by 1.

Determine the minimum number of operations required to transform N into a binary palindromic number.

Note: The binary representation of a number should always be considered without leading zeros.

---

Input Format

A single integer N.

---

Output Format

Print a single integer — the minimum number of operations needed to convert N into a binary palindromic number.

---

Constraints

• 1 ≤ N ≤ 10^9

---

Sample Input 1

2

Sample Output 1

1

Explanation

The binary representation of 2 is 10, which is not a palindrome.

After increasing it by 1, we obtain 3, whose binary representation is 11, a palindrome.

Hence, the answer is 1.

---

Sample Input 2

3

Sample Output 2

0

Explanation

The binary representation of 3 is 11, which is already a palindrome.

---

Sample Input 3

10

Sample Output 3

1

Explanation

The binary representation of 10 is 1010.

Decreasing it by 1 gives 9, whose binary representation is 1001, a palindrome.

Therefore, only one operation is required.

---

Expected Approach

Search outward from N by checking numbers at increasing distances until a binary palindrome is found.

To verify whether a number is binary palindromic:

1. Convert it to binary without leading zeros.
2. Check if the binary string is equal to its reverse.

Time Complexity: O(k × log N), where k is the minimum distance to the nearest binary palindromic number.

Space Complexity: O(log N)