Was It a Cat I Saw

시간 제한1초메모리 제한1024 MB

요약

양의 정수 X가 주어질 때, 이진 표현이 팰린드롬이 되는 정수에 도달하기까지 ±1 연산의 최소 횟수를 각 테스트 케이스마다 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 비트 연산, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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

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

$X$ 에 $1$ 을 더한다.
$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$ 를 이진수로 표현한 문자열이 팰린드롬이 되도록 문제의 연산을 적용할 때, 필요한 연산의 최소 횟수를 출력한다.

예제1

예제 1
입력
```
2
8
1
```
예상 출력
```
1
0
```