동전

한국 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이런 동전을 몇 개 골라 정수 금액을 만들 수 있고, 같은 금액을 만드는 방법이 여러 가지인 경우가 많다. 예를 들어 30원은 1원짜리 30개로도 만들 수 있고, 10원짜리 2개와 5원짜리 2개로도 만들 수 있다.

동전의 종류가 주어질 때 주어진 금액을 만드는 방법의 수를 세는 프로그램을 작성하시오. 같은 종류의 동전은 몇 개든 쓸 수 있고, 고른 순서만 다른 조합은 한 가지 방법으로 센다.

첫 줄에 테스트 케이스의 개수 $T$($1 \le T \le 10$)가 주어진다. 각 테스트 케이스는 세 줄이다. 첫 줄에 동전의 가지 수 $N$($1 \le N \le 20$), 둘째 줄에 $N$가지 동전의 금액이 오름차순으로 공백을 사이에 두고 주어진다. 각 금액은 1 이상 10000 이하의 정수이고, 같은 금액이 두 번 주어지는 경우는 없다. 셋째 줄에 만들어야 할 금액 $M$($1 \le M \le 10000$)이 주어진다.

방법의 수는 항상 $2^{31} - 1$보다 작다.

각 테스트 케이스마다 주어진 $N$가지 동전으로 금액 $M$을 만드는 방법의 수를 한 줄에 하나씩 출력한다.