Description

Lulichuan have a sorted sequences, he want to merge these sequences,every time he can chose $k$ elements to merge, every operating cost the Sum of the sequnces, But the total cost should no more than $T$, so Lulichuan want to know the samllest $k$ .

Format

Input

The first line of input contains an integer T_T, the number of test cases. T_T test cases follow.$(0$ $\leq$ T_T $\leq$ $1000)$ For each test case, the first line consists two integers $N (2\leq N \leq100000)$ and T (∑Ni=1ai. In the next line there are N integers $a_1,a_2,a_3,\dots,aN$$(∀i,0 \leq a_i\leq1000).$

Output

For each test cases, output the smallest $k.$

Samples

1
3 15
3 4 4

Case #1: 3

Hints

K = 2   sum = (3 + 4) + (3 + 4 + 4) > 15
K = 3   sum = 3 + 4 + 4 < 15