e-olymp
Yarışlar

Recursive functions

Hailstone HOTPO

Последовательность града образуется следующим образом:

  • Если n четно, то делим его на 2 и присваиваем n
  • Если n нечетно, то умножим его на 3, прибавим 1 и присваиваем n

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

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

Входные данные

Первая строка содержит количество тестов t (1t100000). Каждый тест следует обработать независимо от других.

Каждый тест состоит из одной строки, содержащей два целых числа. Первое число указывает на номер теста. Вторым является число n (1n100000) - начальное число последовательности.

Выходные данные

Для каждого теста вывести в отдельной строке его номер, пробел, и наибольшее число, встречающееся во всей последовательности начиная и включительно с n.

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
1 1
2 3
3 9999
4 100000
Çıxış verilənləri #1
1 1
2 16
3 101248
4 100000
Mənbə 2012 Greater New York Region Programming Contest, October 28, Problem A