시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 0 | 0 | 0 | 0.000% |
После выхода из строя второго гироскопа, астрономический телескоп "Кеплер" стал непригоден для дальнейшей эксплуатации. 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 ≤ 109) — начальный размер заготовки для солнечной батареи.
На каждый запрос выведите по одному числу — наименьшее время работы лазера, которого смогут добиться учёные.
3 1 1 4 4 3 2
0 0 1
Contest > Russian Code Cup > 2013 > RCC 2013 Elimination Round C번