Kepler

After its second gyroscope failed, the astronomical telescope "Kepler" became unusable. NASA decided to make up for the loss by launching another telescope into space. To supply the telescope with electricity, they decided to use solar panels. The blank for a solar panel is a rectangular panel of size n×m made up of 1×1 cells.

Unfortunately, the panel cannot be delivered to orbit unfolded. To make transport easier, the panel is made of a thin material and can be folded along any cell boundary. The scientists decided that the panel would fly into space folded down to size 1×1.

To do this, they handle the panel blank as follows. If one side of the current blank has even length, the blank can be folded in half along that side, producing a panel half the size (the thickness of the panel is ignored). If some side has odd length (the panel has size (2n+1)×m), they can use a precision laser for time m to cut off a piece of size 1×m, and then fold in half along the side of length 2n. The cut-off piece of the panel is thrown away. As a result, the scientists get a 1×1 panel, which will fly into orbit and unfold there.

The laser runs much longer than all the foldings take. Help them determine the minimum laser operating time they can achieve to fold the original blank into a 1×1 square in the described way.

Note that the size of the panel obtained when the panel is unfolded does not matter; only the laser operating time must be minimized.

The first line contains an integer t (1 ≤ t ≤ 1000), the number of test queries. The next t lines contain the queries. Each query consists of two integers n and m (1 ≤ n, m ≤ 109), the initial size of the solar panel blank.

For each query, output a single number: the minimum laser operating time the scientists can achieve.