One Stroke

Time Limit: 1s

Memory Limit: 65535k

Description

There is a complete binary tree which includes n nodes. Each node on the tree has a weight w, each edge on the tree is directed from the parent node to the child node. Give you a pen, draw from the any node along the directed edge at one stroke. It is required that the sum of those drawn nodes’ s weight is no more than k. How many node can be drawn at most in one stroke?

Input

The first line input an positive integer T(1 ≤ T ≤ 10) indicates the number of test cases. Next, each case occupies two lines. The first line input two positive integers n and k, (1 ≤ k ≤ 10^9 ), The second line input n integers w(1 ≤ w ≤ 10^3 ), indicate the weight of nodes from the first level of the tree and from left to right. 80% test cases: 1 <= n <= 10^3 For 100% test cases: 1 <= n <= 10^6

Output

For each test cases, output one line with the most number of nodes can be drawn in one stroke. If any node likes this doesn’t exists, output -1.

Sample Input

1
5 6
2 3 4 1 7

Sample Output

3

Hint

Source

None

提交代码