The cost of the vegetables is directly proportional to its weight. The vegetable shopkeeper wants to minimize the loss and maximize his profit.

At first, the customer picks n number of vegetables with their sum of weight >= target weight.

Then the shopkeeper can choose any combination of the vegetables picked by the customer. But the sum of weight must remain >= target weight.

The shopkeeper is experienced enough to estimate the weight of any vegetable by looking at it.

Given the target weight and the individual weights of all the vegetables, find the minimum weight loss for the shopkeeper.

weight loss = sum of weight of vegetables chosen by shopkeeper - target weight.

Input

The first line consists of an integer t, the number of test cases. For each test case the first line consists of two integers n and W, the number of vegetables picked by the customer and the target weight respectively. The next line consists of n integers denoting the weights of each vegetable.

Output

For each test case, find the minimum weight loss for the shopkeeper.

Constraints

1 <= t <= 1000

1 <= n <= 20

1 <= weight of each vegetable <= 1000

1 <= W <= 20000

Example

Input:
3
3 40
20 15 15
5 24
5 9 7 10 10
4 40
20 15 15 8

Output:
10
0
3

See also the classical version (with harder test cases): Vegetable Shopkeeper 3