#include <bits/stdc++.h>
using namespace std;
class node{
    public:
    int data;
    node *left, *right;
    node(int data__){
        data = data__;
        left = right = NULL;
    }
};
node* make_tree(vector<int>& v){
    node *head = NULL, *ptr = NULL;
    int n = v.size();
    /*for(int i = 0; i < n; i++){
        cout << v[i] << " ";
    }*/
    if(n == 0){
        return NULL;
    }
    queue<node*> q;
    head = new node(v[0]);
    q.push(head);
    int i = 1;
    while(!q.empty() and i < n){
        node* x = q.front();
        q.pop();
        x -> left = new node(v[i++]);
        if(i < n){
            x -> right = new node(v[i++]);
            //i++;
        }
        q.push(x -> left);
        q.push(x -> right);
    }
    return head;
}
int sum(node* root){
    if(root == NULL){
        return 0;
    }
    return root -> data + sum(root -> left) + sum(root -> right);
}
int sumk(node *root, int k){
    if(root == NULL)
        return 0;
    int ans = 0;
    if(sum(root) == k){
        ans = 1;
    }
    int x = sumk(root -> left, k);
    int y = sumk(root -> right, k);
    return ans + x + y;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        string ss, x;
        cin.ignore();
        getline(cin, ss);
        stringstream s(ss);
        vector<int> v;
        while(s >> x){
            //cout << x << ",";
            v.push_back(stoi(x));
        }
        node* root = make_tree(v);
        int k;
        cin >> k;
        int y = sumk(root, k);
        cout << y ;
    }
return 0;
}