← 返回题目列表

Codeforces · 1279/B

B. 圣诞老人的诗句

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

新年到了!瓦夏准备了一首新年诗句,想在圣诞老人面前背诵。

Vasya 的诗句包含 $$$n$$$ 部分。背诵第 $$$i$$$ 部分需要 $$$a_i$$$ 秒。瓦斯亚无法改变这节经文中各部分的顺序:首先,他背诵需要 $$$a_1$$$ 秒的部分,其次 — 需要 $$$a_2$$$ 秒的部分,依此类推。背诵完这节经文后,瓦夏将获得与他完全背诵的部分数量相等的礼物。

Vasya在背诵经文时最多可以跳过一节经文(如果他跳过超过一节,那么圣诞老人肯定会注意到它)。

圣诞老人聆听 Vasya 的诗句不会超过 $$$s$$$ 秒。例如,如果 $$$s = 10$$$,$$$a = [100, 9, 1, 1]$$$,并且 Vasya 跳过诗句的第一部分,那么他会得到两份礼物。

请注意,可以背诵整节经文(如果有足够的时间)。

确定 Vasya 需要跳过哪一部分才能获得尽可能多的礼物。如果 Vasya 不应跳过任何内容,请打印 0。如果有多个答案,请打印其中任何一个。

您必须处理 $$$t$$$ 测试用例。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \le n \le 10^5, 1 \le s \le 10^9$$$) — 分别是经文中的部分数和圣诞老人​​聆听 Vasya 的最大秒数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 背诵经文每个部分所需的时间。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - Vasya 需要跳过的部分的数量以获得最大数量的礼物。如果 Vasya 不应跳过任何部分,请打印 0。

示例

输入 #1

3
7 11
2 9 1 3 18 1 4
4 35
11 9 10 7
1 8
5

输出 #1

2
1
0

注意

在第一个测试用例中,如果 Vasya 跳过第二部分,那么他会得到三件礼物。

在第二个测试用例中,无论 Vasya 跳过这节经文的哪一部分。

在第三个测试用例中,Vasya 可以背诵整节经文。