今天,樱子正在研究数组。长度为 $$$n$$$ 的数组 $$$a$$$ 被认为是好的,当且仅当:
- 数组 $$$a$$$ 正在递增,这意味着对于所有 $$$2 \le i \le n$$$,$$$a_{i - 1} < a_i$$$;
- 相邻元素之间的差异正在增加,这意味着对于所有 $$$2 \le i < n$$$,$$$a_i - a_{i-1} < a_{i+1} - a_i$$$。
Sakurako 提出了 $$$l$$$ 和 $$$r$$$ 的边界,并希望构建一个最大长度的良好数组,其中 $$$l \le a_i \le r$$$ 代表所有 $$$a_i$$$。
帮助 Sakurako 找到给定 $$$l$$$ 和 $$$r$$$ 的好数组的最大长度。
输入
第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。
每个测试用例的唯一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1\le l\le r\le 10^9$$$)。
输出
对于每个测试用例,输出一个整数 - Sakurako 可以在给定 $$$l$$$ 和 $$$r$$$ 的情况下形成的最长良好数组的长度。
示例
输入 #1
5 1 2 1 5 2 2 10 20 1 1000000000
输出 #1
2 3 1 5 44721
注意
对于 $$$l=1$$$ 和 $$$r=5$$$,一个可能的数组可以是 $$$(1,2,5)$$$。可以证明,对于给定的$$$l$$$和$$$r$$$,不存在长度为$$$4$$$的数组。
对于 $$$l=2$$$ 和 $$$r=2$$$,唯一可能的数组是 $$$(2)$$$。
对于 $$$l=10$$$ 和 $$$r=20$$$,唯一可能的数组是 $$$(10,11,13,16,20)$$$。