#2620 제리 선배 순열

1 s   128 MB  

Description

제리 선배 순열은 다음과 같이 정의 한다. 어떤 수 X가 짝수면 2로 나누고, 홀수면 3을 곱한뒤 1을 더한다.

제리 선배의 추측은 임의의 양의 정수 X로 수열을 시작한다면, 항상 4, 2, 1, 4, 2, 1, 4, 2, 1로 끝난다는 추측이다.

1이 나오면 수열이 끝난 것으로 처리한다.

굉장하지 않은가? 어떤 수 X가 주어졌을때 이 제리 선배 순열에서 가장 큰 값을 찾아 출력하시오.

Input

test case $t$ $(1 \leq t \leq 99999)$가 들어오고 양의 정수 $X$가 들어온다. $(1 \leq X \leq 15 * 10^8)$

Output

양의 정수 X로 시작하는 제리 선배 순열에서 가장 큰 값을 출력하시오.

Sample Input

Sample Output

2
1
3
1
16

Source

2015 ANSI Summer Coding Camp / BOJ 3943 / data set by wowoto9772