헤일스톤 수열

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

• $n$이 짝수라면 $2$로 나눈다.
• $n$이 홀수라면 $3$을 곱한 뒤 $1$을 더한다.

헤일스톤(콜라츠) 추측은, 임의의 양의 정수 $n$에서 수열을 시작하면 항상 $4, 2, 1, 4, 2, 1, \ldots$로 끝난다는 추측이다. 이 문제에서는 $1$이 나오는 순간 수열이 끝난 것으로 본다.

$n$이 주어졌을 때, 이 수열에 나타나는 값 중 가장 큰 값을 찾아 출력하는 프로그램을 작성하시오. 시작값 $n$ 자신도 수열의 일부로 세므로, $n = 1$이면 답은 $1$이다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 100{,}000$)가 주어진다. 다음 $T$개의 줄에는 각각 헤일스톤 수열의 시작값 $n$ ($1 \le n \le 100{,}000$)이 주어진다.

각 테스트 케이스마다 $n$에서 시작하는 헤일스톤 수열에 나타나는 값 중 가장 큰 값을 출력한다.