Tim is a very strong individual. However, the parameters governing his strength are very narrow. He can only lift things that weigh an exact amount. Tim is currently trying to steal as many items from a shelf at the convenience store as he can. Because he is grabbing them all at the same time, he can only steal contiguous sequences of items. For example, say that the weights of items on a shelf are as follows: 3kg, 2kg, -­1kg, and 1kg (Note that weights can be negative, Tim gives off a field that warps the laws of the universe.) Now, in this example, Tim can only lift exactly 2kgs. He has two choices. Either take the single 2kg item, or take the 2kg, -­1kg, and 1kg item which has a total weight of 2kgs. Clearly he wants to steal the maximum amount, so he will take 3 items in this example.

Input

The first line will contain a single integer \(T\) (\(0 \leq T \leq 100\)), which indicates the number of test cases to follow. Every test case begins with two numbers \(N\) and \(W\) (\(0 \leq N \leq 20000\) and \(0 \leq W \leq 100\)) which are the number of items and the weight Tim can lift respectively. Following this will be a line containing \(N\) numbers. Let’s call the \(i\)th number \(N_i\). It is the case that \(-1000 \leq N_i \leq 1000\).

Output

Output every test case on a new line. For each test case, output a single integer: the maximum number of items Tim can steal.

Sample Input

2
4 2
3 2 -1 1
5 3
-2 3 3 1 -4

Sample Output

3
4