You are given an integer array a_1, a_2, ..., a_n and integer k.

In one step you can 

  * either choose some index i and decrease a_i by one (make a_i = a_i - 1); 
  * or choose two indices i and j and set a_i equal to a_j (make a_i = a_j). 



What is the minimum number of steps you need to make the sum of array ∑_{i=1}^{n}{a_i} ≤ k? (You are allowed to make values of array negative).

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The first line of each test case contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ k ≤ 10^{15}) — the size of array a and upper bound on its sum.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the array itself.

It's guaranteed that the sum of n over all test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print one integer — the minimum number of steps to make ∑_{i=1}^{n}{a_i} ≤ k.

Example

Input


4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10


Output


10
0
2
7

Note

In the first test case, you should decrease a_1 10 times to get the sum lower or equal to k = 10.

In the second test case, the sum of array a is already less or equal to 69, so you don't need to change it.

In the third test case, you can, for example: 

  1. set a_4 = a_3 = 1; 
  2. decrease a_4 by one, and get a_4 = 0. 

As a result, you'll get array [1, 2, 1, 0, 1, 2, 1] with sum less or equal to 8 in 1 + 1 = 2 steps.

In the fourth test case, you can, for example: 

  1. choose a_7 and decrease in by one 3 times; you'll get a_7 = -2; 
  2. choose 4 elements a_6, a_8, a_9 and a_{10} and them equal to a_7 = -2. 

As a result, you'll get array [1, 2, 3, 1, 2, -2, -2, -2, -2, -2] with sum less or equal to 1 in 3 + 4 = 7 steps.
1
84 781
403 867 729 928 240 410 849 95 651 852 230 209 358 596 576 230 924 448 288 19 680 470 839 107 931 809 347 903 399 185 840 326 338 758 584 385 862 140 256 537 677 195 593 349 588 452 771 995 853 27 765 878 312 93 411 846 537 426 593 288 506 167 721 84 189 213 490 958 937 522 171 563 995 166 258 408 638 107 720 553 318 758 302 8
 1
77 816
131 139 214 578 23 543 45 617 821 886 910 646 883 517 929 804 72 151 349 472 511 413 28 434 969 58 239 672 349 261 137 87 362 462 193 587 979 846 814 164 30 305 863 487 515 994 389 177 439 928 905 455 481 583 444 221 872 947 715 532 569 945 344 340 244 158 189 767 179 342 399 239 508 105 370 621 150
 1
91 734
815 147 433 982 71 972 593 712 205 267 802 60 80 482 616 963 177 457 763 874 695 988 235 413 519 805 341 453 240 541 428 39 202 206 496 69 505 80 155 333 935 71 184 253 656 722 173 331 890 959 446 429 305 939 338 531 998 577 888 610 282 276 326 784 766 28 448 55 399 775 889 997 482 233 567 465 42 754 438 360 138 750 146 712 249 630 819 941 798 999 895
 1
95 902
670 783 456 537 294 406 958 479 769 924 864 137 865 889 560 816 383 471 790 922 575 646 47 762 278 287 841 950 246 386 197 970 581 466 212 501 577 26 208 583 703 528 284 514 101 788 409 799 650 122 148 328 878 402 112 943 821 114 500 422 269 696 863 246 111 420 473 385 342 238 112 325 726 257 176 359 311 30 529 36 814 927 816 636 614 196 859 630 802 442 446 305 899 44 591
 1
98 282
103 948 349 26 241 933 394 571 476 785 441 397 658 308 801 940 760 29 717 343 99 341 389 797 955 322 662 763 654 781 933 185 622 960 363 84 786 998 331 572 236 837 553 874 376 362 649 482 860 718 54 298 574 987 16 943 71 292 615 829 460 301 358 245 585 438 24 561 151 416 88 81 86 571 805 67 862 698 811 772 389 185 798 799 469 547 109 474 72 128 717 893 38 928 741 644 641 625
 1
174 243
7 7 1 5 9 8 7 5 8 6 10 4 9 3 5 3 2 10 5 9 10 3 5 2 2 6 8 9 2 6 7 6 10 4 9 8 8 9 5 1 9 1 2 7 1 10 8 6 4 6 2 4 10 4 4 3 9 8 2 2 6 9 8 2 5 9 5 2 9 6 9 4 10 9 10 5 8 2 10 7 6 10 4 5 3 4 3 1 10 5 8 2 2 3 3 1 2 9 7 9 5 9 4 4 10 7 10 5 8 8 6 2 6 10 2 8 10 6 4 4 1 5 2 4 6 3 6 7 1 2 3 4 1 10 9 10 2 1 2 4 10 10 2 7 2 6 2 1 10 1 4 3 2 8 4 1 1 9 7 10 2 5 2 4 2 5 6 7 3 1 9 8 1 10
 1
77 340
616 230 33 414 33 520 881 594 173 951 566 507 792 941 244 477 260 277 162 731 833 342 13 81 726 616 890 188 708 365 427 991 14 596 878 102 258 187 135 52 891 147 50 396 576 104 947 85 895 912 439 133 948 536 253 734 375 819 797 356 141 201 482 964 885 426 359 22 452 403 694 267 64 304 884 813 308
 1
15 11
1 1 4 4 4 4 2 2 5 4 4 4 1 5 1

80
 86
 107
 108
 106
 44
 81
 8

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  int T;
  cin >> T;
  vector<ll> ans(T, 1LL << 60);
  for (int t = 0; t < T; t++) {
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    sort(a.begin(), a.end());
    ll A = 0;
    for (int i = 0; i < n; i++) {
      A += a[i];
    }
    if (A <= k) {
      ans[t] = 0;
      continue;
    }
    vector<ll> sum(n);
    sum[0] = 0;
    if (n == 1) {
      ans[t] = a[0] - k;
      continue;
    }
    if (n > 1) {
      sum[1] = a[1];
      if (n > 2) {
        for (int i = 2; i < n; i++) {
          sum[i] = sum[i - 1] + a[i];
        }
      }
    }
    for (ll y = 1; y < n; y++) {
      ll x = 0;
      if ((sum[n - y - 1] - k) % (y + 1) == 0) {
        x += (sum[n - y - 1] - k) / (y + 1);
      } else {
        x += ((sum[n - y - 1] - k) / (y + 1) + 1);
      }
      x += a[0];
      x = max((ll)0, x);
      ans[t] = min(ans[t], x + y);
    }
  }
  for (int t = 0; t < T; t++) {
    cout << ans[t] << endl;
  }
  return 0;
}
