← 返回题目列表

Codeforces · 2182/B

B. 年糕

中文机器翻译题面 查看原题

Monocarp 要去烤一个新年蛋糕。

蛋糕必须包含 至少一个 层。蛋糕顶层的大小必须为$$$1$$$;它下面的层的大小必须是$$$2$$$;下面的层必须是 $$$4$$$,依此类推(除了顶部之外,每一层的大小都是其上面层的两倍)。

此外,每一层都必须覆盖白巧克力或黑巧克力。为了覆盖一层 $$$k$$$ 大小的层,Monocarp 将需要 $$$k$$$ 公斤的巧克力。每一层都必须覆盖一种类型的巧克力,并且 这些类型必须交替 (如果某层覆盖有黑巧克力,则其正下方的层和其正上方的层都必须覆盖有白巧克力,反之亦然)。

Monocarp 有 $$$a$$$ 公斤白巧克力和 $$$b$$$ 公斤黑巧克力。他想要计算蛋糕可以包含的最大层数,以确保他有足够的两种类型的巧克力。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le 10^6$$$)。

输出

对于每个测试用例,输出一个整数——蛋糕的最大可能层数。

示例

输入
复制

7
1 1
1 2
3 1
4 3
5 2
1000000 1000000
1000000 1

输出
复制

1
2
2
2
3
20
2

注意

在第一个示例中,Monocarp 可以烘焙一层大小为 $$$1$$$ 的蛋糕,并在其上覆盖任何类型的巧克力。

在第二个示例中,Monocarp 可以烘焙两层蛋糕:顶层为 $$$1$$$ 大小的白巧克力,下面一层为 $$$2$$$ 大小的黑巧克力。

在第三个示例中,Monocarp 可以烘焙两层蛋糕:顶层为 $$$1$$$ 大小的黑巧克力,下面一层为 $$$2$$$ 大小的白巧克力。

在第四个示例中,Monocarp 可以烘焙两层蛋糕:顶层为 $$$1$$$ 大小的黑巧克力,下面一层为 $$$2$$$ 大小的白巧克力。请注意,对于三层蛋糕,其中顶层尺寸为 $$$1$$$ 且其下方的尺寸为 $$$2$$$ 均为黑巧克力,而底层尺寸为 $$$4$$$ 为白巧克力,则该蛋糕无效,因为层的类型必须交替。