시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 207 53 47 31.333%

문제

상근이는 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
W3sicHJvYmxlbV9pZCI6IjUzOTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNWNcdWI3N2NcdWNlMjAiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgM24rMVx1YzczY1x1Yjg1YyBcdWM3MjBcdWJhODVcdWQ1NWMgXHViYjM4XHVjODFjXHVjNzc4IFx1Y2Y1Y1x1Yjc3Y1x1Y2UyMCBcdWNkOTRcdWNlMjFcdWM3NDQgXHVkNDgwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIwOThcdWJiMzRcdWQzMTBcdWM2NDAgXHViYzI3XHVjOTA0XHVjNzQ0IFx1YWQ2Y1x1YjllNFx1ZDU4OFx1YjJlNC4gXHViMDk4XHViYjM0XHVkMzEwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWJiMzRcdWQ1NWNcdWQ3ODggXHVkMDZjXHVhY2UwLCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIDFtIFx1YWMwNFx1YWNhOVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJhNGRcdWM3NzQgXHViNmE0XHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWFkNmNcdWJhNGRcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IGlcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOWRkXHVjMjE4XHViYzg4XHVjOWY4IFx1YWQ2Y1x1YmE0ZCBtXHVjNWQwXHViMjk0IG1cdWJjODhcdWM5ZjhcdWM2NDAgbVwvMlx1YmM4OFx1YzlmOCBcdWFkNmNcdWJhNGRcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YmMyN1x1YzkwNFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1YmFhOFx1YjRlMCBcdWQ2NDBcdWMyMThcdWJjODhcdWM5ZjggXHVhZDZjXHViYTRkIG5cdWM1ZDBcdWIyOTQgblx1YmM4OFx1YzlmOFx1YzY0MCAzbisxXHViYzg4XHVjOWY4IFx1YWQ2Y1x1YmE0ZFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHViYzI3XHVjOTA0XHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzkxXHVkNDg4XHVjNzQ0IFx1YjRlNFx1YWNlMCBcdWMyZTBcdWM3ODVcdWMwZGQgXHVkNjU4XHVjNjAxXHVkNjhjXHVjNWQwIFx1YWMwMFx1YzExYyBcdWQ2NGRcdWJjZjRcdWI5N2MgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjRlNFx1YWNlMFx1YWMwOCBcdWJjMjlcdWJjOTVcdWM3NzQgXHViM2M0XHVjODAwXHVkNzg4IFx1YzBkZFx1YWMwMVx1YjA5OFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmMyN1x1YzkwNFx1Yzc0NCBcdWM4MDFcdWM4MDhcdWQ3ODggXHVjNzk4XHViNzdjXHVjMTFjIFx1Y2M5OFx1Yzc0YyBOXHVhYzFjIFx1YWQ2Y1x1YmE0ZFx1YjljYyBcdWI0ZTRcdWFjZTBcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmMyN1x1YzkwNFx1Yzc0NCBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YWMxY1x1YjljYyBcdWM3OTBcdWI5NzRcdWJhNzQgXHVjYzk4XHVjNzRjIE5cdWFjMWMgXHVhZDZjXHViYTRkXHViOWNjIFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NDQgXHViNGU0XHVhY2UwIFx1YWMwOCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgTlx1Yzc3NCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMCAmbGU7IE4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWJjMjdcdWM5MDRcdWM3NDQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWFjMWMgXHVjNzkwXHViOTc0XHViYTc0IFx1YjQxOFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTM5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbGxhdHoiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBwcm9jZXNzIHRvIHNvbHZlIHRoZSBDb2xsYXR6IGNvbmplY3R1cmUsIGJldHRlciBrbm93biBhcyB0aGUgM24gKyAxIHByb2JsZW0sIENhcmwgY3JlYXRlZCBhIHBoeXNpY2FsIG1vZGVsIHdpdGggd29vZCBhbmQgcm9wZXMuIEEgd29vZGVuIGJhciBjb250YWlucyBhIGhvbGUgZm9yIGV2ZXJ5IG5hdHVyYWwgbnVtYmVyIGZyb20gMSB0byBpblx1ZmIwMW5pdHkgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBGb3IgZXZlcnkgZXZlbiBudW1iZXIgbSB0aGVyZSBpcyBhIHJvcGUgY29ubmVjdGluZyB0aGUgbXRoIGhvbGUgd2l0aCBob2xlIG1cLzIuIEZvciBldmVyeSBvZGQgbnVtYmVyIG4gdGhlcmUgaXMgYSByb3BlIGNvbm5lY3RpbmcgdGhlIG50aCBob2xlIHdpdGggaG9sZSAzbiArIDEuPFwvcD5cclxuXHJcbjxwPkZvciBhbiBpbXBvcnRhbnQgY29uZmVyZW5jZSB3aGVyZSBDYXJsIHBsYW5zIHRvIGVsYWJvcmF0ZSBvbiBoaXMgcmVzdWx0cywgaGUgd2FudHMgdG8gYnJpbmcgaGlzIHN0cnVjdHVyZSwgYnV0IGl0IGlzIHRvbyBsYXJnZSB0byBcdWZiMDF0IGluIGhpcyBiYWcuIFNvIGhlIGRlY2lkZWQgdG8gc2F3IG9cdWZiMDAgdGhlIHBhcnQgb2YgdGhlIGJhciBjb250YWluaW5nIHRoZSBcdWZiMDFyc3QgTiBob2xlcyBvbmx5LiBIb3cgbWFueSByb3BlcyB3aWxsIGhlIG5lZWQgdG8gY3V0PzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBjYXNlIGhhcyB0aGUgZm9sbG93aW5nIGZvcm1hdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGFuIGludGVnZXIgTiwgc2F0aXNmeWluZyAwICZsZTsgTiAmbGU7IDEwPHN1cD45PFwvc3VwPi48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgaW4gdGhlIGlucHV0LCB0aGUgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIG51bWJlciwgb24gYSBzaW5nbGUgbGluZTogdGhlIG51bWJlciBvZiByb3BlcyB0aGF0IG5lZWQgdG8gYmUgY3V0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==