Coins

Korean coins come in denominations of 1, 5, 10, 50, 100, and 500 won. Picking several coins adds up to an integer amount, and the same amount usually has more than one combination. For example, 30 won is thirty 1 won coins, or two 10 won coins together with two 5 won coins.

Given the denominations, write a program that counts how many ways there are to make a given amount. Each denomination can be used any number of times, and two selections that differ only in the order the coins were picked count as one way.

The first line has the number of test cases $T$ ($1 \le T \le 10$). Each test case takes three lines. The first line has the number of denominations $N$ ($1 \le N \le 20$). The second line has the $N$ coin values in increasing order, separated by spaces. Every value is an integer between 1 and 10000, and no value is given twice. The third line has the amount $M$ ($1 \le M \le 10000$) to make.

The number of ways is always smaller than $2^{31} - 1$.

For each test case, print the number of ways to make the amount $M$ with the given $N$ denominations, one per line.