22119번 - Кеплер 다국어

문제

После выхода из строя второго гироскопа, астрономический телескоп "Кеплер" стал непригоден для дальнейшей эксплуатации. NASA решило возместить эту потерю и запустить в космос другой телескоп. Для того, чтобы обеспечить телескоп электричеством, решено было использовать солнечные батареи. Заготовка для солнечной батареи представляет собой прямоугольную панель размером n×m, состоящую из ячеек 1×1.

К сожалению, невозможно доставить батарею на орбиту в развёрнутом состоянии. Для облегчения транспортировки панель сделана из тонкого материала и может сгибаться вдоль любой границы ячеек. Учёные решили, что батарея полетит в космос сложенной до размера 1×1.

Для этого они поступают с заготовкой для батареи следующим образом: если одна из сторон текущей заготовки имеет чётную длину, то можно сложить заготовку вдоль неё пополам, получается панель вдвое меньшего размера (толщиной панели можно пренебречь). Если же какая-то из сторон имеет нечётную длину (панель имеет размер (2n+1)×m), то они могут сверхточным лазером за время m отрезать от неё кусок размера 1×m, а затем сложить пополам вдоль стороны длиной 2n. Отрезанный кусок панели выбрасывается. В итоге у учёных получается панель 1×1, которая полетит на орбиту и там развернётся.

Лазер работает намного дольше, чем происходят все складывания. Помогите им определить, какого наименьшего времени работы лазера они могут добиться, чтобы свернуть указанным образом исходную заготовку в квадрат размером 1×1.

Обратите внимание, что размер батареи, которая получится в результате разворачивания панели, значения не имеет, необходимо минимизировать время работы лазера.

입력

Первая строка содержит целое число t (1 ≤ t ≤ 1000) — число тестовых запросов. Следующие t строк содержат сами запросы. Каждый запрос состоит из двух целых чисел n и m (1 ≤ n, m ≤ 10⁹) — начальный размер заготовки для солнечной батареи.

출력

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

제한

힌트