You are given coins of different denominations, represented by an array - coins of size n. You are also given a value - target. Find the different number of combinations that make up the amount target. Assume that you have infinite number of each kind of coin.

Example

coins: [5, 2, 4]
target: 13
Result: 3
Explanation: The three ways are-
2, 2, 2, 2, 5
2, 2, 4, 5
4, 4, 5

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has two lines:

• Two space-separated integers ‘n’ and ‘target’.
• n space-separated integers denoting the available denominations.

Output Format

For each test case, the output contains a line with one integer denoting the number of possible combinations.

Sample Input

3
3 13
5 2 4
3 28
2 5 4
4 28
1 2 4 5

Expected Output

3
16
163

Constraints

1 <= T <= 10
1 <= n <= 1000
1 <= target <= 3000
0 <= Ci <= 2000
0 <= number of combinations <= 109