该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

xlc  最近在玩一款沙盒游戏。

简单起见，我们可以把游戏的地图看作是一个无限长宽的平面网格，网格上可以放置的东西只有两种："石块"与"水"。我们把网格中"一个 $1\times 1$ 的格子"称为"一格"。

每个格子的都可以放置一个石块来构建地图，这些石块可以放置在任意位置（允许悬空，即不要求每个方块下面都要有方块）。石块放置后就固定住了，不会变化位置。

水比较特殊，类似于现实世界的水，游戏中的水被放置后会向下、左、右三个方向自然流动，如果遇到了石块就会停止往那个方向流动。比如下图中，同样是三个石块，左边的摆放方式可以使用固定一格水，而右边的石块就没法留住任何的水，水会向右流下去。

输入格式

接下来一共$T$行，每一行为空格隔开的两个整数 $n,m$。

对于 $30\%$ 的数据：$1\leq n \leq 10^5,1\leq m \leq 10^9$。

对于 $70\%$ 的数据：$1\leq n \leq 10^7,1\leq m \leq 10^{13}$。

对于 $100\%$ 的数据：$1\leq T \leq 100,1\leq n \leq 8\times 10^9,1\leq m \leq 10^{18}$。

输出格式

对于每组询问，输出一个整数。

如果她能用这 $n$ 个石块固定至少 $m$ 格水，请输出她最多能固定多少水；

否则请输出她至少需要多少个石块。

样例

5
4 1
1 4
1 10007
1 998244353
998244353 1

2
5
202
63192
249122946574974976