시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2036 824 661 41.677%

문제

헤일스톤 수열은 다음과 같이 정의 한다.

- n이 짝수라면, 2로 나눈다.

- n이 홀수라면, 3을 곱한 뒤 1로 더한다.

헤일스톤 추측은 임의의 양의 정수 n으로 수열을 시작한다면, 항상 4, 2, 1, 4, 2, 1,...로 끝난다는 추측이다. 이 문제에서는 1이 나오면 수열이 끝난 것으로 처리한다.

n이 주어졌을 때, 이 수열에서 가장 큰 값을 찾아 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 다음 줄부터 T개의 줄에는 헤일스톤 수열의 시작값 n이 주어진다. (1 ≤ n ≤ 100,000)

출력

각각의 테스트 케이스에 대해서, n으로 시작하는 헤일스톤 수열에서 가장 큰 값을 출력한다.

예제 입력 1

4
1
3
9999
100000

예제 출력 1

1
16
101248
100000
W3sicHJvYmxlbV9pZCI6IjM5NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ZTRcdWM3N2NcdWMyYTRcdWQxYTQgXHVjMjE4XHVjNWY0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWQ1ZTRcdWM3N2NcdWMyYTRcdWQxYTQgXHVjMjE4XHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+LSBuXHVjNzc0IFx1YzlkZFx1YzIxOFx1Yjc3Y1x1YmE3NCwgMlx1Yjg1YyBcdWIwOThcdWIyMDhcdWIyZTQuPFwvcD5cclxuPHA+LSBuXHVjNzc0IFx1ZDY0MFx1YzIxOFx1Yjc3Y1x1YmE3NCwgM1x1Yzc0NCBcdWFjZjFcdWQ1NWMgXHViNGE0IDFcdWI4NWMgXHViMzU0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ1ZTRcdWM3N2NcdWMyYTRcdWQxYTQgXHVjZDk0XHVjZTIxXHVjNzQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IG5cdWM3M2NcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNFx1YmE3NCwgXHVkNTZkXHVjMGMxIDQsIDIsIDEsIDQsIDIsIDEsLi4uXHViODVjIFx1YjA1ZFx1YjA5Y1x1YjJlNFx1YjI5NCBcdWNkOTRcdWNlMjFcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgMVx1Yzc3NCBcdWIwOThcdWM2MjRcdWJhNzQgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YjA1ZFx1YjA5YyBcdWFjODNcdWM3M2NcdWI4NWMgXHVjYzk4XHViOWFjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRuXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NDQgXHVjYzNlXHVjNTQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmxlOyBUICZsZTsgMTAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDVlNFx1Yzc3Y1x1YzJhNFx1ZDFhNCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjMmRjXHVjNzkxXHVhYzEyIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgblx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVkNWU0XHVjNzdjXHVjMmE0XHVkMWE0IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhhaWxzdG9uZSBIT1RQTyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGhhaWxzdG9uZSBzZXF1ZW5jZSBpcyBmb3JtZWQgaW4gdGhlIGZvbGxvd2luZyB3YXk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SWYgbiBpcyBldmVuLCBkaXZpZGUgaXQgYnkgMiB0byBnZXQgbiYjMzk7PFwvbGk+XHJcblx0PGxpPmlmIG4gaXMgb2RkLCBtdWx0aXBseSBpdCBieSAzIGFuZCBhZGQgbCB0byBnZXQgbiYjMzk7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SXQgaXMgY29uamVjdHVyZWQgdGhhdCBmb3IgYW55IHBvc2l0aXZlIGludGVnZXIgbnVtYmVyIG4sIHRoZSBzZXF1ZW5jZSB3aWxsIGFsd2F5cyBlbmQgaW4gdGhlIHJlcGVhdGluZyBjeWNsZTogNCwgMiwgMSwgNCwgMiwgMSwuLi4uIFN1ZmZpY2UgdG8gc2F5LCB3aGVuIG4gPT0gMSwgd2Ugd2lsbCBzYXkgdGhlIHNlcXVlbmNlIGhhcyBlbmRlZC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSB0aGUgbGFyZ2VzdCB2YWx1ZSBpbiB0aGUgc2VxdWVuY2UgZm9yIGEgZ2l2ZW4gbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgc2hvdWxkIGJlIHByb2Nlc3NlZCBpZGVudGljYWxseSBhbmQgaW5kZXBlbmRlbnRseS48XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIG9mIGlucHV0IGNvbnNpc3Rpbmcgb2YgdHdvIHNwYWNlIHNlcGFyYXRlZCBkZWNpbWFsIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlciBpcyB0aGUgZGF0YSBzZXQgbnVtYmVyLiBUaGUgc2Vjb25kIGludGVnZXIgaXMgbiwgKGwgJmxlOyBuICZsZTsgMTAwLCAwMDApLCB3aGljaCBpcyB0aGUgc3RhcnRpbmcgdmFsdWUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQgY29uc2lzdGluZyBvZiB0aGUgZGF0YSBzZXQgbnVtYmVyLCBhIHNpbmdsZSBzcGFjZSwgYW5kIHRoZSBsYXJnZXN0IHZhbHVlIGluIHRoZSBzZXF1ZW5jZSBzdGFydGluZyBhdCBhbmQgaW5jbHVkaW5nIG4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d