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$$$)。
输出
对于每个测试用例,输出一个整数——蛋糕的最大可能层数。
示例
输入复制
71 11 23 14 35 21000000 10000001000000 1
输出复制
12223202
注意
在第一个示例中,Monocarp 可以烘焙一层大小为 $$$1$$$ 的蛋糕,并在其上覆盖任何类型的巧克力。
在第二个示例中,Monocarp 可以烘焙两层蛋糕:顶层为 $$$1$$$ 大小的白巧克力,下面一层为 $$$2$$$ 大小的黑巧克力。
在第三个示例中,Monocarp 可以烘焙两层蛋糕:顶层为 $$$1$$$ 大小的黑巧克力,下面一层为 $$$2$$$ 大小的白巧克力。
在第四个示例中,Monocarp 可以烘焙两层蛋糕:顶层为 $$$1$$$ 大小的黑巧克力,下面一层为 $$$2$$$ 大小的白巧克力。请注意,对于三层蛋糕,其中顶层尺寸为 $$$1$$$ 且其下方的尺寸为 $$$2$$$ 均为黑巧克力,而底层尺寸为 $$$4$$$ 为白巧克力,则该蛋糕无效,因为层的类型必须交替。