Hôm nay là sinh nhật của Cá Nóc. Vì biết Cá Nóc rất thích chơi với những con số nên một người bạn tri kỉ của cậu ấy - Thợ Săn đã tặng cho Cá Nóc T hộp quà đặc biệt. Nhưng tất cả hộp quà đều bị khóa và đi kèm với mỗi hộp là một số nguyên dương n. Thợ săn còn tặng cho Cá Nóc một công thức như sau: F(n) = n/2 nếu n chẵn, F(n) = 3n+1 nếu n lẻ.

Thợ Săn nói với Cá Nóc rằng: với số n đi kèm trong mỗi hộp quà, hãy biến đổi n thành F(n) một số lần cho tới khi n = 1. Số lần thực hiện phép biến đổi chính là mã số để mở khóa hộp quà đó. Ví dụ với một hộp quà có n = 5, các phép biển đổi được biểu diễn như sau:

• 5 → 16 → 8 → 4 → 2 → 1.

• Số phép biến đổi thực hiện là 5

Bởi vì Cá Nóc rất thông minh, cậu ấy có thể đoán ra được ngay là số lần thực hiện phép biến đổi là hữu hạn. Nhưng việc tìm ra mã số mất khá nhiều thời gian. Mặc dù rất muốn xem bên trong những hộp quà có gì nhưng Cá Nóc lại bận phải tiếp đón những người bạn của mình. Nên Cá Nóc muốn nhờ các bạn tìm ra con số tương ứng để mở hộp quà.

Input:

• Dòng đầu tiên chứ số nguyên dương T(T ≤ 1000).

• T dòng tiếp theo, mỗi dòng chứa một số nguyên dương ni(ni ≤ 1000000) là số đi kèm cùng hộp quà thứ i.

Output:

• Ghi kết quả ra T dòng, dòng thứ i ghi ra con số dùng để mở hộp quà thứ i.

Sample Input

3

5

1

2

Sample Output

``` 5

0

1 '''