Asiar likes chocolates a lot. One day, she was walking by the road to her school. Suddenly a magician appeared and said, "HAHAHA!!! I am the great magician NN (secret name). I appear once in every thousand years when the sky is as white as milk. You are in great luck today because I will grant your one wish.. You can ask for anything! So tell me, what is your wish ?? HAHAHA!!!" Sudden appearance of the great magician NN made Asiar scared and confused. She could think about only one thing. Yeah! among all the things she could wish for, she wished for chocolates ! A lot of chocolates !........ (Well, who are we to judge?) But seeing Asiar in school dress, the magician thought about motivating Asiar in studies too. So the great magician NN said, "Okay. I will give you N box of chocolates. Whenever you will take all the chocolate from the box, the box will disappear. After that N-1 box will stay. Then again, you will take all the chocolates from another box and that box will disappear. Then for the 3rd time, you will chose a box and again that box will disappear. Whenever you chose a box, you will have to take all the chocolates from that box." Now, the magician NN gives the real puzzle: The sum of all the chocolates Asiar will take have to be equal to a number S which the great magician NN will tell Asiar beforehand. The question is, how many ways can Asiar take chocolates? Two ways are different, if one of the selected box is different.

Input

First line will contain the number of test cases, T. Then there will be T lines, each containing two integer N and S. Then there will be N integers Ai. Ai represents the number of chocolate in the ith chocolate in the box.

1 ≤ T ≤ 100

3 ≤ N ≤ 1000

0 ≤ Ai ≤ 1000000000

Output

For each test case, output the required answer in a line. See the sample test case for better understanding.