你需要构造一个函数 $F(x)$，定义域为实数区间 $[0, n]$，值域为实数区间 $[0, m]$，且满足对任意 $0 \le a < c < b \le n$，有 $F(a) < F(c) < F(b)$ 且若 $c = (a + b) / 2$ 则满足 $F(a) + F(b) > 2F(c)$。问最多存在几个点 $(X, Y)$ 满足 $X$ 为整数且 $F(X) = Y$。

为了让题难一点，你需要处理多组询问。

输入格式

第一行一个整数 $q$，表示询问组数。

接下来 $q$ 行每行两个整数 $n, m$，表示一组询问。

输出格式

输出 $q$ 行，每行一个整数，表示答案。

数据范围

本题采用子任务评测。

• 对于 $20\%$ 的数据，满足 $q = 15, n, m \le 5$。
• 对于 $40\%$ 的数据，满足 $n, m \le 200$。
• 对于 $60\%$ 的数据，满足 $n, m \le 1000$。
• 对于另外 $20\%$ 的数据，满足时限为 $4\text{s}$。
• 对于 $100\%$ 的数据，满足 $1 \le q \le 10000$ 且 $1 \le n, m \le 3000$。

说明

样例解释：

可以证明以下两个函数是样例对应的最优解，当然可能存在其它函数也是最优解：

$$y = \frac{x(x+1)}{6} \quad (0 \le x \le 3)$$ $$y = x^2 \quad (0 \le x \le 1)$$

不用注意常数因子带来的影响。std看起来是个斯拉夫怪人。

样例

样例输入 1

2
3 2
1 1

样例输出 1

3
2