콜라츠

3n + 1 문제로도 잘 알려진 콜라츠 추측(Collatz conjecture)을 연구하던 칼은 나무와 밧줄로 물리적 모형을 만들었다. 하나의 나무 막대에는 왼쪽에서 오른쪽으로 1부터 무한대까지 모든 자연수에 대응하는 구멍이 하나씩 뚫려 있다. 모든 짝수 $m$에 대해 $m$번째 구멍과 $m/2$번째 구멍을 잇는 밧줄이 하나 있다. 모든 홀수 $n$에 대해 $n$번째 구멍과 $3n + 1$번째 구멍을 잇는 밧줄이 하나 있다.

칼은 자신의 연구 결과를 발표할 중요한 학회에 이 구조물을 가져가고 싶지만, 가방에 넣기에는 너무 크다. 그래서 그는 막대에서 처음 $N$개의 구멍만 남도록 잘라내기로 했다. 이때 몇 개의 밧줄을 끊어야 하는가?

입력의 첫 번째 줄에는 뒤따르는 테스트 케이스의 개수를 나타내는 정수 하나가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 정수 $N$이 하나 주어진다. ($0 \le N \le 10^9$)

각 테스트 케이스마다, 끊어야 하는 밧줄의 개수를 한 줄에 하나씩 출력한다.