Град 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$.

Примеры