====== 동전 ======

===== 풀이 =====
  * [[ps:problems:boj:3067]]과 완전히 동일한 문제. 풀이는 그쪽을 참고

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 9084. 동전".

- Problem link: https://www.acmicpc.net/problem/9084
- Solution link: http://www.teferi.net/ps/problems/boj/9084

Tags: [DP]
"""


def main():
    T = int(input())
    for _ in range(T):
        N = int(input())  # pylint: disable=unused-variable
        coins = [int(x) for x in input().split()]
        M = int(input())

        dp = [0] * (M + 1)
        dp[0] = 1
        for coin in coins:
            for i, dp_prev in zip(range(coin, M + 1), dp):
                dp[i] += dp_prev

        print(dp[M])


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}