Steps to Nearest Binary Palindrome

You are given a positive integer n. A positive integer is a binary palindrome if its binary representation, written without leading zeros, reads the same forwards and backwards. For example, 9 (1001) and 5 (101) are binary palindromes, but 10 (1010) is not.

In one step you may add 1 to n or subtract 1 from it. Return the minimum number of steps needed to turn n into a binary palindrome.

Examples

Example 1

Input: n = 10
Output: 1
Explanation: 10 is 1010. One step down gives 9 = 1001, a palindrome.

Example 2

Input: n = 7
Output: 0
Explanation: 7 is 111, already a palindrome.

Example 3

Input: n = 12
Output: 3
Explanation: 12 is 1100. The nearest palindromes are 9 (1001) and 15 (1111), both 3 steps away.