← 返回题目列表

Codeforces · 2008/C

C. 最长的好数组

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

今天,樱子正在研究数组。长度为 $$$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)$$$。