시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 137 39 34 31.193%

문제

상근이는 3n+1으로 유명한 문제인 콜라츠 추측을 풀기 위해 나무판와 밧줄을 구매했다. 나무판의 길이는 무한히 크고, 왼쪽에서 오른쪽으로 1m 간격으로 구멍이 뚤려져 있다. i번째 구멍은 자연수 i를 의미한다. 모든 짝수번째 구멍 m에는 m번째와 m/2번째 구멍을 연결하는 밧줄이 연결되어 있다. 또, 모든 홀수번째 구멍 n에는 n번째와 3n+1번째 구멍을 연결하는 밧줄이 연결되어 있다.

상근이는 자신의 작품을 들고 신입생 환영회에 가서 홍보를 하려고 한다. 하지만, 나무판의 길이가 무한대이기 때문에, 들고갈 방법이 도저히 생각나지 않았다. 따라서, 상근이는 밧줄을 적절히 잘라서 처음 N개 구멍만 들고가려고 한다. 이 때, 밧줄을 최소 몇 개만 자르면 처음 N개 구멍만 있는 나무판을 들고 갈 수 있을까?

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 문제에서 설명한 N이 포함된 한 줄로 이루어져 있다. (0 ≤ N ≤ 109)

출력

각 테스트 케이스에 대해서, 밧줄을 최소 몇 개 자르면 되는지 출력한다.

예제 입력

3
12
240
3600

예제 출력

10
200
3000

힌트