# Appreciation

/*
 * Problem :: 9084 / 동전
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 전형적인 DP 문제이다
 *   + C[i] = i번째 동전의 금액
 *     dp[i][j] = 1~i 번째 동전으로 금액 j를 만드는 방법의 수
 *     라고 했을 때, 점화식은 아래와 같다
 *     # dp[i][j] = dp[i-1][j] + dp[i][j-C[i]] if j-C[i] >= 0
 *       -> 1~i 번째 동전으로 금액 j를 만드는 방법의 수
 *          =
 *          1~(i-1) 번째 동전으로 금액 j를 만드는 방법의 수 <= i번째 동전을 사용안한 방법의 수
 *          +
 *          1~i 번째 동전으로 금액 j-C[i]를 만드는 방법의 수 <= i번째 동전을 사용한 방법의 수
 *
 * Point
 * - 사실 입력에서 동전의 금액이 정렬되어 있지 않아도 상관없다
 *   + 오름차순, 내림차순 및 임의의 순서로 주어져도 DP 에는 아무런 영향이 없다
 *
 * - dp[i][j] 가 아닌 dp[j] 로도 풀 수 있다
 *   + i번째 동전으로 금액 1~j를 만드는 방법의 수를 구하면
 *     자연스레 dp[j] = 1~i 번째 동전으로 금액 j를 만드는 방법의 수가 된다
 *     # dp[j] 로 알고리즘을 짜면
 *       아래 코드에서 dp[i][j] = dp[i-1][j] 부분을 생략할 수 있다
 *       -> 점화식을 보면 dp[i-1][...], dp[i][...] 부분만 필요하고
 *          dp[0~(i-2)] 부분은 더이상 필요치 않다는 것을 알 수 있다
 *
 * - dp[i][0] = 1 이다
 *   + 2원, 3원 금액의 동전이 주어졌다고 하자
 *     금액 | 2 3 (사용된 동전의 개수)
 *       0 | 0 0
 *       1 | 0 0
 *       2 | 1 0
 *       3 | 0 1
 *       4 | 2 0
 *       5 | 1 1
 *       ...
 *       # 2 = 2*1 + 3*0
 *         3 = 2*0 + 3*1
 *         4 = 2*2 + 3*0
 *         5 = 2*1 + 3*1
 *         이므로
 *         0 = 2*0 + 3*0 도 1가지 방법으로 인정해주어야 한다
 *
 * - DP 배열과 순서를 맞추어 주기 위해
 *   동전의 금액을 저장하는 배열을 N+1 크기로 선언해서
 *   1~N 번째에 차례로 넣어주었다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        int N; cin >> N;
        int C[N+1];
        for (int i=1; i<=N; i++) {
            cin >> C[i];
        }
        int M; cin >> M;

        // Process
        int dp[N+1][M+1];
        memset(dp, 0, sizeof(dp));
        for (int i=1; i<=N; i++) { /* i 번째 동전을 사용 */
            dp[i][0] = 1; /* 금액 0원을 만드는 방법은
                           * 각 금액별 동전들을 모두 0개씩 사용하는 방법밖에 없음 */
            for (int j=1; j<=M; j++) { /* 금액 j원을 만들기 */
                dp[i][j] += dp[i-1][j]; /* i 번째 동전을 사용하지 않고
                                         * 금액 j원을 만드는 방법 */
                if (j-C[i] >= 0) { /* j-C[i] >= 0 인 경우에 i 번째 동전 사용 가능 */
                    dp[i][j] += dp[i][j-C[i]]; /* i 번째 동전을 사용하여
                                                * 금액 j원을 만드는 방법 */
                }
            }
        }

        // Control : Output
        cout << dp[N][M] << endl;
    }
}

// Helper Functions
/* None */