B. Популяция

Ограничение времени: 2 с
Ограничение памяти: 256 M


Расскажу я всем знакомым
Тяжело быть насекомым! 

Дюна

Ни для кого не секрет, что студенты ОНУ больше всех любят биологию. Но мало кто знает, что именно студент кафедры Увеселительной Теории Василий Простонародьев вывел новую разновидность саранчи – саранча сиракузская. Это милое насекомое живёт в стаях и питается всем, что попадётся – рой саранчи способен в считанные минуты съесть молодые посевы рапса, конопли, а так же он не гнушается мелкими рептилиями и млекопитающими. Единственная проблема заключается в том, что насекомые не выносят одиночества – оставшись одна, саранча тут же умирает от тоски. Кроме того многочисленные наблюдения позволили, студенту вывести интересную закономерность: популяция саранчи в стае меняется каждый день и не зависит ни от количества пищи, ни от времени года, а лишь от количества насекомых, находящихся в стае в предыдущий день. Если вчера популяция составляла N особей и N чётно, то сегодня их, увы, останется N/2. Зато если N было нечётно, то сегодня нас порадует задорным жужжанием аж 3*N-1 насекомое. Сейчас Василий наблюдает новую колонию саранчи. К сожалению, он не может назвать точного числа насекомых в ней, а значит, предсказать дальнейшее развитие популяции. Единственное, в чём он уверен, это то, что количество насекомых не меньше натурального числа A и не больше натурального числа B. Осчастливьте студента Простонародьева известием, что данная колония будет жить вечно, либо с прискорбием сообщите, какое максимальное число дней она может просуществовать. Но говорите только правду! Вася чувствует, когда ему лгут.

Ввод. Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 100000). Каждая из следующих T строк содержит по одному запросу – пару чисел A и B (1 ≤ A ≤ B ≤ 11111).

Вывод. На каждый запрос выведите -1, если есть вариант, при котором колония проживёт вечно. Иначе выведите максимальное количество дней, которые она может протянуть.

Идея – Игорь Евгеньевич Мазурок

Примеры

Входные данные Результат работы
2
1 2
3 4
1
4
About the post author Igor Mazurok (5 Posts)

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine KBIS Software Developer

Author Info

Igor Mazurok

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine
KBIS Software Developer

Добавить комментарий