您是最著名的流媒体平台上的普通聊天用户。当然,有时候您只是想冷静一下并发送垃圾邮件。
更准确地说,您想要向大小为 $$$k$$$ 的表情三角形发送垃圾邮件。它由 $$$2k-1$$$ 消息组成。第一条消息包含一个表情符号,第二条消息包含两个表情符号,...,第 $$$k$$$ 个表情符号包含 $$$k$$$ 表情符号,第 $$$k+1$$$ 个表情符号包含 $$$k-1$$$ 表情符号,...,最后一个消息包含一个表情符号。
例如,$$$k=3$$$ 的表情三角形由 $$$5$$$ 消息组成:
当然,大多数频道都有自动审核功能。在您连续发送至少 $$$x$$$ 表情符号后,当前聊天的自动主持人将立即禁止您(您可以假设您是聊天中的唯一用户)。现在你感兴趣的是——在被禁止之前你会写多少条消息?或者也许您根本不会被禁止(即会写入所有 $$$2k-1$$$ 消息并成功完成您的表情三角)?请注意,如果您因撰写消息而被禁止,则该消息也会被计算在内。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来的 $$$t$$$ 行描述了测试用例。
测试用例的唯一行包含整数 $$$k$$$ 和 $$$x$$$ ($$$1 \le k \le 10^9; 1 \le x \le 10^{18}$$$)。
输出
对于每个测试用例,打印您在被禁止之前将写入的消息数,对应的值 $$$k$$$ 和 $$$x$$$。
示例
输入 #1
7 4 6 4 7 1 2 3 7 2 5 100 1 1000000000 923456789987654321
输出 #1
3 4 1 4 3 1 1608737403
注意
我们来分析一下示例的测试用例。
1. 在第一个测试用例中,您编写了三个分别包含 $$$1$$$、$$$2$$$ 和 $$$3$$$ 表情的消息,并且由于 $$$1 + 2 + 3 \ge 6$$$,之后您将被禁止。
2. 在第二个测试用例中,您编写了四条分别包含 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$ 表情的消息,并且由于 $$$1 + 2 + 3 + 4 \ge 7$$$,因此您将被禁止。
3. 在第三个测试用例中,您编写一条包含 $$$1$$$ 表情的消息。它不会让您被禁止,因为 $$$1 < 2$$$,但您已经完成了表情三角形的发布。这样您就成功写了一封邮件。
4. 在第四个测试用例中,您编写了四条分别包含 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$2$$$ 表情的消息,并且由于 $$$1 + 2 + 3 + 2 \ge 7$$$,因此您将被禁止。
5. 在第五个测试用例中,您编写了三个分别包含 $$$1$$$、$$$2$$$ 和 $$$1$$$ 表情的消息。它不会让您被禁止,因为 $$$1 + 2 + 1 < 5$$$,但您已经完成了表情三角形的发布。这样你就成功写了三条消息。
6. 在第六个测试用例中,由于 $$$x = 1$$$,因此您在发送第一条消息后就会被禁止。
7. 第七个测试用例太大,无法分析,所以我们跳过它。