Град HOTPO

Послідовність града утворюється наступним чином:

• Якщо $n$ парне, то ділимо його $2$ і присвоюємо $n$

• Якщо $n$ непарне, то домножуємо його на $3$, додаємо $1$ і присвоюємо $n$

Стверджуючи, що для будь-якого натурального числа $n$ вказана послідовність завжди закінчується циклом: $4,2,1,4,2,1,...$. Достатньо сказати, що при $n=1$ послідовність закінчується.

Напишіть програму, яка визначить найбільше значення в послідовності для заданого числа $n$.

Вхідні дані

Перший рядок містить кількість тестів $t(1\le t\le 10^5)$. Кожен тест потрібно опрацювати незалежно від інших.

Кожен тест складається з одного рядка, що містить два цілих числа. Перше число вказує на номер тесту. Друге - це число $n(1\le n\le 10^5)$ — початкове число послідовності.

Вихідні дані

Для кожного тесту виведіть в окремому рядку его номер, пропуск, і найбільше число, яке зустрічається у всій послідовності починаючи з $n$.

Приклади