You have \(N\) pills of characteristic values \(a_1, a_2, ..., a_n\).

On each day \(i\) you can take the \(i\)th pill and increase your health by \(a_i\) points \(H := H+a_i\) or Do nothing and take 1 point of damage \(H := H-1\) , where \(H\) is a value deenoting your health. You die if your health becomes zero. Initially \(H = V \) (where \(V\) is a value given in the input).

What is the minimum number of pills you should take to survive for \(N\) days.

Input

Each test consists of multiple test cases. The first line contains a single integer \(t\) ( \(1 \leq t \leq 10^4\) ) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers \(N \) and \(V\) where \(1 \leq N , V \leq 200000\)

The second line of each test case contains \(N \) space seperated integers \(a_1,a_2,...,a_N\) ( \(1 \leq a_i \leq 200000\))

The sum of \(N\) over all test cases does not exceed \(200000\).

Output

For each test case print the minimum number of pills you should take to survive for \(N\) days.