33887번 - Was It a Cat I Saw

문제 제목의 문장을 거꾸로 읽어보자. 그렇다. 당신은 팰린드롬을 좋아한다.

팰린드롬(Palindrome)이란 앞으로 읽어도, 뒤로 읽어도 같은 문자열을 의미한다. 양의 정수 $X$가 주어질 때, 당신은 연산마다 아래의 연산 중 하나를 골라 시행할 수 있다.

1. $X$에 $1$을 더한다.
2. $X$에 $1$을 뺀다. 단, $X>1$를 만족해야 한다.

$X$를 이진수로 표현한 문자열이 팰린드롬이 되도록 원하는 만큼 연산을 적용할 때, 필요한 연산의 최소 횟수를 구해보자. 이때 $X$를 이진수로 표현했을 때 앞쪽의 불필요한 $0$들(leading zero)은 무시한다. 예를 들어, $X=9=1001_{(2)}$는 이진수로 표현했을 때 팰린드롬이지만, $X=8=1000_{(2)}$는 이진수로 표현했을 때 팰린드롬이 아니다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\leq T \leq 30)$

두 번째 줄부터 $T$줄에 걸쳐 양의 정수 $X$가 주어진다. $(1\leq X \leq 10^9)$

각 테스트 케이스마다 $X$를 이진수로 표현한 문자열이 팰린드롬이 되도록 문제의 연산을 적용할 때, 필요한 연산의 최소 횟수를 출력한다.