시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB0000.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 ≤ nm ≤ 109) — начальный размер заготовки для солнечной батареи.

출력

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

예제 입력 1

3
1 1
4 4
3 2

예제 출력 1

0
0
1