시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 188 50 44 33.083%

문제

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

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

입력

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

출력

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

예제 입력 1

3
12
240
3600

예제 출력 1

10
200
3000
W3sicHJvYmxlbV9pZCI6IjUzOTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNWNcdWI3N2NcdWNlMjAiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgM24rMVx1YzczY1x1Yjg1YyBcdWM3MjBcdWJhODVcdWQ1NWMgXHViYjM4XHVjODFjXHVjNzc4IFx1Y2Y1Y1x1Yjc3Y1x1Y2UyMCBcdWNkOTRcdWNlMjFcdWM3NDQgXHVkNDgwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIwOThcdWJiMzRcdWQzMTBcdWM2NDAgXHViYzI3XHVjOTA0XHVjNzQ0IFx1YWQ2Y1x1YjllNFx1ZDU4OFx1YjJlNC4gXHViMDk4XHViYjM0XHVkMzEwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWJiMzRcdWQ1NWNcdWQ3ODggXHVkMDZjXHVhY2UwLCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIDFtIFx1YWMwNFx1YWNhOVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJhNGRcdWM3NzQgXHViNmE0XHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWFkNmNcdWJhNGRcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IGlcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOWRkXHVjMjE4XHViYzg4XHVjOWY4IFx1YWQ2Y1x1YmE0ZCBtXHVjNWQwXHViMjk0IG1cdWJjODhcdWM5ZjhcdWM2NDAgbVwvMlx1YmM4OFx1YzlmOCBcdWFkNmNcdWJhNGRcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YmMyN1x1YzkwNFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YmFhOFx1YjRlMCBcdWQ2NDBcdWMyMThcdWJjODhcdWM5ZjggXHVhZDZjXHViYTRkIG5cdWM1ZDBcdWIyOTQgblx1YmM4OFx1YzlmOFx1YzY0MCAzbisxXHViYzg4XHVjOWY4IFx1YWQ2Y1x1YmE0ZFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViYzI3XHVjOTA0XHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzkxXHVkNDg4XHVjNzQ0IFx1YjRlNFx1YWNlMCBcdWMyZTBcdWM3ODVcdWMwZGQgXHVkNjU4XHVjNjAxXHVkNjhjXHVjNWQwIFx1YWMwMFx1YzExYyBcdWQ2NGRcdWJjZjRcdWI5N2MgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjRlNFx1YWNlMFx1YWMwOCBcdWJjMjlcdWJjOTVcdWM3NzQgXHViM2M0XHVjODAwXHVkNzg4IFx1YzBkZFx1YWMwMVx1YjA5OFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmMyN1x1YzkwNFx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVjNzk4XHViNzdjXHVjMTFjIFx1Y2M5OFx1Yzc0YyBOXHVhYzFjIFx1YWQ2Y1x1YmE0ZFx1YjljYyBcdWI0ZTRcdWFjZTBcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJjMjdcdWM5MDRcdWM3NDQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWFjMWNcdWI5Y2MgXHVjNzkwXHViOTc0XHViYTc0IFx1Y2M5OFx1Yzc0YyBOXHVhYzFjIFx1YWQ2Y1x1YmE0ZFx1YjljYyBcdWM3ODhcdWIyOTQgXHViMDk4XHViYjM0XHVkMzEwXHVjNzQ0IFx1YjRlNFx1YWNlMCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIE5cdWM3NzQgXHVkM2VjXHVkNTY4XHViNDFjIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDAgJmxlOyBOICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViYzI3XHVjOTA0XHVjNzQ0IFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHVhYzFjIFx1Yzc5MFx1Yjk3NFx1YmE3NCBcdWI0MThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjUzOTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb2xsYXR6IiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGUgcHJvY2VzcyB0byBzb2x2ZSB0aGUgQ29sbGF0eiBjb25qZWN0dXJlLCBiZXR0ZXIga25vd24gYXMgdGhlIDNuICsgMSBwcm9ibGVtLCBDYXJsIGNyZWF0ZWQgYSBwaHlzaWNhbCBtb2RlbCB3aXRoIHdvb2QgYW5kIHJvcGVzLiBBIHdvb2RlbiBiYXIgY29udGFpbnMgYSBob2xlIGZvciBldmVyeSBuYXR1cmFsIG51bWJlciBmcm9tIDEgdG8gaW5cdWZiMDFuaXR5IGZyb20gbGVmdCB0byByaWdodC4gRm9yIGV2ZXJ5IGV2ZW4gbnVtYmVyIG0gdGhlcmUgaXMgYSByb3BlIGNvbm5lY3RpbmcgdGhlIG10aCBob2xlIHdpdGggaG9sZSBtXC8yLiBGb3IgZXZlcnkgb2RkIG51bWJlciBuIHRoZXJlIGlzIGEgcm9wZSBjb25uZWN0aW5nIHRoZSBudGggaG9sZSB3aXRoIGhvbGUgM24gKyAxLjxcL3A+XHJcblxyXG48cD5Gb3IgYW4gaW1wb3J0YW50IGNvbmZlcmVuY2Ugd2hlcmUgQ2FybCBwbGFucyB0byBlbGFib3JhdGUgb24gaGlzIHJlc3VsdHMsIGhlIHdhbnRzIHRvIGJyaW5nIGhpcyBzdHJ1Y3R1cmUsIGJ1dCBpdCBpcyB0b28gbGFyZ2UgdG8gXHVmYjAxdCBpbiBoaXMgYmFnLiBTbyBoZSBkZWNpZGVkIHRvIHNhdyBvXHVmYjAwIHRoZSBwYXJ0IG9mIHRoZSBiYXIgY29udGFpbmluZyB0aGUgXHVmYjAxcnN0IE4gaG9sZXMgb25seS4gSG93IG1hbnkgcm9wZXMgd2lsbCBoZSBuZWVkIHRvIGN1dD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIHRlc3QgY2FzZSBoYXMgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIE4sIHNhdGlzZnlpbmcgMCAmbGU7IE4gJmxlOyAxMDxzdXA+OTxcL3N1cD4uPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBudW1iZXIsIG9uIGEgc2luZ2xlIGxpbmU6IHRoZSBudW1iZXIgb2Ygcm9wZXMgdGhhdCBuZWVkIHRvIGJlIGN1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=