题目描述

有 $n$ 艘船出发探索海洋深处，这些船的编号 $1$ 到 $n$，第 $i$ 艘船的耐久度为 $a_i$。

不幸的是，当他们进入海洋深处时，惊动了这片海洋的霸主——小田！

小田对入侵者进行了 $k$ 次攻击，首先，他攻击第一艘船，然后是最后一艘，然后再次攻击第一艘，依此类推。

小田的每次攻击都会使船的耐久度降低 $1$，当船的耐久度降为 $0$时，船会沉没，不再受到攻击（因此该船不再是第一艘或最后一艘，小田只会攻击尚未沉没的船）。

如果所有的船都沉没了，或者小田已经攻击了 $k$ 次，那么他会离开。

例如，如果 $n = 4, k = 5, a = [1,2,4,3]$，则会发生以下情况：

1. 小田攻击第一艘船，其耐久度变为 $0$，现在$a = [2, 4, 3]$;
2. 小田攻击最后一艘船，现在 $a = [2, 4, 2]$;
3. 小田攻击第一艘船，现在 $a = [1, 4, 2]$;
4. 小田攻击最后一艘船，其耐久度变为 $1$，现在 $a = [1, 4, 1]$;
5. 小田攻击第一艘船， 现在 $a = [4, 1]$.

请问，小田最终击沉了多少艘船？

输入

第一行包含一个整数 $t$，代表测试样例的组数。 ($1 \le t \le 5000$)

对于每组测试样例：

第一行输入两个正整数 $n,k(1 \le n \le 2 \times 10^5, 1 \le k \le 10^{15})$；

第二行输入 $n$ 个正整数 $a_i(1 \le a_i \le 10^9)$；

数据保证所有的 $n$ 总和不超过$2 \cdot 10^5$

输出

对于每组测试样例：

输入一行，为小田击沉的船只数量

6
4 5
1 2 4 3
4 6
1 2 4 3
5 20
2 7 1 8 2
2 2
3 2
2 15
1 5
2 7
5 2

2
3
5
0
2
2