1279_B. Verse For Santa_28566
New Year is coming! Vasya has prepared a New Year's verse and wants to recite it in front of Santa Claus.

Vasya's verse contains n parts. It takes a_i seconds to recite the i-th part. Vasya can't change the order of parts in the verse: firstly he recites the part which takes a_1 seconds, secondly — the part which takes a_2 seconds, and so on. After reciting the verse, Vasya will get the number of presents equal to the number of parts he fully recited.

Vasya can skip at most one part of the verse while reciting it (if he skips more than one part, then Santa will definitely notice it).

Santa will listen to Vasya's verse for no more than s seconds. For example, if s = 10, a = [100, 9, 1, 1], and Vasya skips the first part of verse, then he gets two presents.

Note that it is possible to recite the whole verse (if there is enough time). 

Determine which part Vasya needs to skip to obtain the maximum possible number of gifts. If Vasya shouldn't skip anything, print 0. If there are multiple answers, print any of them.

You have to process t test cases.

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of test cases.

The first line of each test case contains two integers n and s (1 ≤ n ≤ 10^5, 1 ≤ s ≤ 10^9) — the number of parts in the verse and the maximum number of seconds Santa will listen to Vasya, respectively.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the time it takes to recite each part of the verse.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case print one integer — the number of the part that Vasya needs to skip to obtain the maximum number of gifts. If Vasya shouldn't skip any parts, print 0.

Example

Input


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


Output


2
1
0

Note

In the first test case if Vasya skips the second part then he gets three gifts.

In the second test case no matter what part of the verse Vasya skips.

In the third test case Vasya can recite the whole verse.
#include <bits/stdc++.h>
using namespace std;
int main() {
  int que;
  cin >> que;
  while (que--) {
    int a[100005], prefix[100005] = {0};
    long long n, s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> a[i];
    int id = 0;
    int right = 0;
    int ans = 0;
    int ansLeft = 0;
    long long sum = 0;
    int maxx = a[0];
    int countt1 = 0;
    long long sum1 = 0;
    int countt = 0;
    for (int i = 0; i < n; i++) {
      sum += a[i];
      if (sum <= s) {
        if (a[i] >= maxx) id = i;
        maxx = max(a[i], maxx);
      } else {
        if (sum + a[i + 1] - maxx && i + 1 < n) {
          if (a[i] > maxx)
            ans = i + 1;
          else
            ans = id + 1;
        } else
          ans = 0;
        break;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

3
7 11
2 9 1 3 18 1 4
4 35
11 9 10 7
1 8
5
 7
10 11
2 2 2 6 5 3 4 4 4 100000000
4 102
98 1 3 99
4 103
5 98 1 97
11 1000000000
100000000 100000002 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 99999999
8 90
20 8 20 20 20 20 1 1
3 1000000000
1000000000 1000000000 1000000000
11 1000000000
1 3 5 1000000000 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 1
50 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 4
5 1000000000
2 999999999 999999998 1000000000 1000000000
4 1000000000
2 999999999 999999998 1000000000
6 1000000000
1 1000000000 999999999 1000000000 1000000000 1000000000
5 1000000000
1 999999999 999999998 1 1000000000
 1
6 1000000000
1 999999999 999999998 1 999999999 1
 1
6 1000000000
999999999 999999999 999999999 1 1 1
 1
5 999999999
1000000000 999999999 1000000000 1000000000 1000000000
 1
9 1000000000
999999999 9 999999990 999999999 999999999 999999999 999999999 9 999999999
 1
4 1000000000
999999998 1000000000 2 999999999
 1
24 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
7 1000000000
500000000 999999999 500000000 1000000000 1000000000 1000000000 294967297
 1
4 1000000000
500000000 1000000000 500000000 300000000
 1
5 10
1 8 10 1 10
 5
5 1000000000
2 999999999 999999998 1000000000 1000000000
4 1000000000
2 999999999 999999998 1000000000
6 1000000000
1 1000000000 999999999 1000000000 1000000000 1000000000
5 1000000000
1 999999999 999999998 1 1000000000
10 1000000000
1 999999998 1 999999999 1 1000000000 1000000000 1000000000 1000000000 1000000000
 1
4 1000000000
2 999999999 999999998 1000000000
 1
7 1000000000
1 1 1000000000 1 1 1000000000 1000000000
 1
6 1000000000
99 999999999 123000 900000000 900000000 12
 1
24 1000000000
999999996 2 2 2 2 2 999999990 999999992 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1
5 850068230
198760381 693554507 54035836 441101531 438381286
 1
30 333807280
241052576 14440862 145724506 113325577 417499967 8081113 32419669 424487323 580244209 553065169 569140721 84508456 315856135 145805595 650034885 140825197 17745281 106540897 28580639 111465247 106976325 17650089 649905801 145670799 21998257 220175998 567636481 73795226 10024990 230718118
 1
10 1000000000
5 6 7 4 1000000000 10 74 1000000000 1000000000 1000000000
 1
6 1000000000
999999999 999999999 1 999999999 1 1
 1
6 999999999
1000000000 999999999 1000000000 1000000000 1000000000 1
 1
8 999999999
1 999899998 1 1000000000 1 1000000000 1000000000 1
 1
5 999999999
1000000000 1 1000000000 1000000000 1000000000
 1
10 10
1 9 2 3 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 2
9 1000000000
999999999 9 999999990 999999999 999999999 999999999 999999999 9 999999999
8 1000000000
999999999 999999990 999999999 999999999 999999999 999999999 999999999 999999999
 6
5 1000000000
2 999999999 999999998 1000000000 1000000000
4 1000000000
2 999999999 999999998 1000000000
6 1000000000
1 1000000000 999999999 1000000000 1000000000 1000000000
5 1000000000
1 999999999 999999998 1 1000000000
10 1000000000
1 999999999 1 999999997 1 1000000000 1000000000 1000000000 1000000000 1000000000
4 999999999
1000000000 1 1000000000 1000000000
 1
8 1000000000
999999996 2 2 2 2 2 999999990 999999992
 1
4 1000000000
1 1000000000 999999998 1000000000
 1
4 1000000000
999999999 1000000000 1 999999999
 1
25 2
2 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 1
1 10
4
 1
5 1000000000
2 999999999 999999998 1000000000 1000000000
 1
4 1000000000
1 1000000000 999999999 1000000000
 1
4 2
1000000000 1 1000000000 1000000000
 1
8 1000000000
1 1000000000 999999999 1000000000 294967296 1000000000 1000000000 1000000000
 1
50 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000001 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
6 1000000000
1 999999999 999999998 1 1012258995 1
 1
5 9
1 8 10 1 10
 5
5 1000000000
2 999999999 999999998 1000000000 1000000000
4 1000000000
2 999999999 999999998 1000000000
6 1000000000
1 1000000000 184318275 1000000000 1000000000 1000000000
5 1000000000
1 999999999 999999998 1 1000000000
10 1000000000
1 999999998 1 999999999 1 1000000000 1000000000 1000000000 1000000000 1000000000
 1
10 1000000000
5 0 7 4 1000000000 10 74 1000000000 1000000000 1000000000
 1
8 999999999
1 360305987 1 1000000000 1 1000000000 1000000000 1
 2
9 1000000000
999999999 9 999999990 999999999 999999999 999999999 999999999 9 999999999
8 1000000000
999999999 999999990 999999999 999999999 1587762833 999999999 999999999 999999999
 6
5 1000000000
2 999999999 999999998 1000000000 1000000000
4 1000000000
2 999999999 999999998 1000000000
6 1000000000
1 1000000000 999999999 1000000000 1000000000 1000000000
5 1000000000
2 999999999 999999998 1 1000000000
10 1000000000
1 999999999 1 999999997 1 1000000000 1000000000 1000000000 1000000000 1000000000
4 999999999
1000000000 1 1000000000 1000000000
 1
1 10
5
 3
7 11
3 9 1 3 18 1 4
4 35
11 9 10 7
1 8
5
 3
7 11
3 9 1 3 18 1 4
4 35
4 9 10 7
1 8
5
 1
6 1000000000
999999999 999999999 999999999 1 1 2
 1
4 999999999
1000000000 999999999 1000000000 1000000000 1000000000
 1
9 1000000010
999999999 9 999999990 999999999 999999999 999999999 999999999 9 999999999
 1
24 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 110000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
7 1000000000
500000000 999999999 500000000 1000000001 1000000000 1000000000 294967297
 1
4 1000000000
166138173 1000000000 500000000 300000000
 1
4 1000000000
2 1054207185 999999998 1000000000
 1
6 1000000000
99 999999999 25219 900000000 900000000 12
 1
24 1000000000
999999996 2 3 2 2 2 999999990 999999992 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1
5 850068230
198760381 718595817 54035836 441101531 438381286
 1
30 333807280
241052576 14440862 145724506 113325577 417499967 8081113 32419669 424487323 580244209 553065169 569140721 84508456 315856135 145805595 650034885 140825197 17745281 106540897 28580639 111465247 106976325 17650089 649905801 145670799 21998257 220175998 390589630 73795226 10024990 230718118
 1
6 1244825309
1000000000 999999999 1000000000 1000000000 1000000000 1
 1
5 999999999
1010000000 1 1000000000 1000000000 1000000000
 1
4 1000000000
1 1100000000 999999998 1000000000
 1
4 1000000000
879646039 1000000000 1 999999999
 1
25 2
2 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1010000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 1
4 1000010000
1 1000000000 999999999 1000000000
 1
8 1000000000
1 1000000000 98690276 1000000000 294967296 1000000000 1000000000 1000000000
 1
50 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000001 100000000 100000000 100000000 100000000 000000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
6 1000000000
1 1693700912 999999998 1 1012258995 1
 1
4 999999999
1000000000 999999999 1000000000 1000000000 1010000000
 1
9 1000000010
999999999 9 999999990 999999999 999999999 999999999 999999999 9 335574820
 1
24 1
2 1 100000100 100000000 100000000 100000000 100000000 100000000 100000000 100000000 110000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
4 1000000100
166138173 1000000000 500000000 300000000
 5
5 1000000000
2 999999999 242505307 1000000000 1000000000
4 1000000000
2 999999999 999999998 1000000000
6 1000000000
1 1000000000 184318275 1000000000 1000000000 1000000000
5 1000000000
1 999999999 999999998 1 1000000000
10 1000000000
1 999999998 1 999999999 1 1000000000 1000000000 1000000000 1000000000 1000000000
 1
6 1000000000
91 999999999 25219 900000000 900000000 12
 1
24 1000000000
999999996 2 3 2 2 2 999999990 999999992 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
 1
5 850068230
198760381 718595817 66039011 441101531 438381286
 1
30 333807280
241052576 14440862 145724506 113325577 417499967 8081113 32419669 424487323 580244209 553065169 569140721 84508456 315856135 145805595 650034885 140825197 17745281 106540897 28580639 111465247 106976325 17650089 649905801 145670799 34389058 220175998 390589630 73795226 10024990 230718118
 1
5 1000000000
5 0 7 4 1000000000 10 74 1000000000 1000000000 1000000000
 1
8 999999999
1 655102112 1 1000000000 1 1000000000 1000000000 1
 1
5 999999999
1010000000 0 1000000000 1000000000 1000000000
 1
4 1000000000
1 1100000000 999999998 1000100000
 1
25 2
2 1 1 1000010000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1010000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
 1
1 10
2
 1
4 1000110000
1 1000000000 999999999 1000000000
 1
8 1000000000
1 1000000000 98690276 1000000000 294967296 1000000000 1000000000 1000010000
 1
50 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000010 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000001 100000000 100000000 100000000 100000000 000000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
4 1708271163
1000000000 999999999 1000000000 1000000000 1010000000
 1
9 1000000010
999999999 9 999999990 999999999 999999999 1476745735 999999999 9 335574820
 1
24 1
3 1 100000100 100000000 100000000 100000000 100000000 100000000 100000000 100000000 110000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
4 1000000100
166138173 1000000010 500000000 300000000
 1
6 1000000000
91 999999999 25219 900000000 900000000 4
 1
24 1000000000
999999996 2 3 2 2 2 999999990 999999992 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0
 1
5 1531535681
198760381 718595817 66039011 441101531 438381286
 1
30 333807280
241052576 14440862 145724506 113325577 417499967 8081113 32419669 281979110 580244209 553065169 569140721 84508456 315856135 145805595 650034885 140825197 17745281 106540897 28580639 111465247 106976325 17650089 649905801 145670799 34389058 220175998 390589630 73795226 10024990 230718118
 1
5 1000000000
5 0 7 4 1000010000 10 74 1000000000 1000000000 1000000000
 1
8 999999999
1 655102112 1 1000000000 1 1000000000 1000000010 1
 1
5 999999999
1011000000 0 1000000000 1000000000 1000000000
 1
4 1000000000
2 1100000000 999999998 1000100000
 1
25 2
2 1 1 1000010000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1010000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000100 1000000000
 1
1 9
2
 1
4 1000110000
2 1000000000 999999999 1000000000
 1
8 1000000000
1 1000000000 98690276 1000000000 294967296 1100000000 1000000000 1000010000
 3
7 11
3 9 1 3 18 1 1
4 35
4 9 10 7
1 8
5
 1
50 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000010 100000000 100000000 100000000 100000000 100100000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000001 100000000 100000000 100000000 100000000 000000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
9 1000000010
999999999 9 999999990 999999999 999999999 1476745735 630539938 9 335574820
 1
24 1
3 1 100000100 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
6 1000000000
91 1495486292 25219 900000000 900000000 4
 1
24 1000000000
999999996 2 3 2 2 2 999999990 999999992 1 1 1 1 1 1 1 2 1 1 0 1 1 1 1 0
 1
30 206961452
241052576 14440862 145724506 113325577 417499967 8081113 32419669 281979110 580244209 553065169 569140721 84508456 315856135 145805595 650034885 140825197 17745281 106540897 28580639 111465247 106976325 17650089 649905801 145670799 34389058 220175998 390589630 73795226 10024990 230718118
 1
5 1000000000
10 0 7 4 1000010000 10 74 1000000000 1000000000 1000000000
 1
8 999999999
1 655102112 1 1000010000 1 1000000000 1000000010 1
 1
25 2
2 1 1 1000011000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1010000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000100 1000000000
 1
1 9
1
 1
4 1000110000
2 1000000000 802152789 1000000000
 1
8 1000000100
1 1000000000 98690276 1000000000 294967296 1100000000 1000000000 1000010000
 1
50 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000010 100000000 100000000 100000000 100000000 100100000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000001 000000000 100000000 100000000 100000000 000000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
9 1000000010
999999999 9 999999990 999999999 999999999 1780703501 630539938 9 335574820
 1
24 1
3 1 100000100 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000100 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
6 1000000000
91 1495486292 25219 900000000 900000000 1
 1
24 1000000000
999999996 2 3 2 2 2 999999990 999999992 1 1 1 1 1 1 1 2 1 1 0 1 2 1 1 0
 1
30 206961452
241052576 14440862 145724506 113325577 417499967 8081113 32419669 281979110 580244209 553065169 569140721 84508456 315856135 145805595 650034885 140825197 17745281 106540897 28580639 111465247 207869094 17650089 649905801 145670799 34389058 220175998 390589630 73795226 10024990 230718118
 1
8 999999999
1 655102112 1 1000010000 1 1000000100 1000000010 1
 1
25 4
2 1 1 1000011000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1010000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000100 1000000000
 1
1 9
0
 1
4 1000110001
2 1000000000 802152789 1000000000
 1
8 1000000100
1 1000000000 98690276 1000000000 294967296 1100000100 1000000000 1000010000
 1
50 1
2 1 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000010 100000000 100000000 100001000 100000000 100100000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000001 000000000 100000000 100000000 100000000 000000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
9 1000000010
999999999 9 999999990 999999999 999999999 1780703501 178742556 9 335574820
 1
24 1
3 1 100000100 100000000 100000000 100100000 100000000 100000000 100000000 100000000 100000000 100000000 100000100 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
 1
6 1000000000
151 1495486292 25219 900000000 900000000 1
 1
24 1000000000
999999996 2 3 2 2 2 999999990 999999992 1 1 1 1 1 1 1 2 1 2 0 1 2 1 1 0
 1
30 206961452
241052576 14440862 145724506 113325577 417499967 8081113 32419669 281979110 580244209 553065169 569140721 84508456 428877168 145805595 650034885 140825197 17745281 106540897 28580639 111465247 207869094 17650089 649905801 145670799 34389058 220175998 390589630 73795226 10024990 230718118

2
1
0
 4
4
2
2
1
1
4
 1
 2
2
2
2
 2
 1
 1
 1
 2
 1
 2
 2
 3
 2
2
2
2
4
 2
 3
 2
 1
 2
 1
 5
 1
 1
 4
 1
 2
 1
1
 2
2
2
2
2
1
 1
 2
 2
 1
 0
 2
 2
 1
 2
 1
 2
 3
 2
2
2
2
4
 5
 4
 1
1
 2
2
2
2
2
1
 0
 2
1
0
 2
0
0
 1
 1
 1
 1
 2
 2
 2
 2
 1
 2
 1
 1
 1
 2
 2
 1
 2
 2
 1
 2
 1
 1
 1
 2
 2
2
2
2
4
 2
 1
 2
 1
 5
 4
 1
 2
 1
 0
 2
 2
 1
 1
 1
 1
 2
 2
 1
 2
 1
 5
 4
 1
 2
 1
 0
 2
 2
 2
0
0
 1
 1
 1
 2
 1
 1
 5
 4
 1
 0
 2
 2
 1
 1
 1
 2
 1
 1
 4
 4
 0
 2
 2
 1
 1
 1
 2
 1
 1
