#include <bits/stdc++.h>
using namespace std;
int main() {
using ivector = vector<int>;
using imatrix = vector<ivector>;
const int M = 100, P = 10;
const ivector multiplier = {-1,0,1};
const bool do_test = true;
ivector arr(P), pow3(P+1,1);
for (int x = 1; x <= P; ++x)
pow3[x] = 3*pow3[x-1];
const function<int(int,int)> recursive_solution = [&](int n, int k) {
if (n == 0)
return int(k == 0);
int ans = 0;
for (int p = n-1, a = arr[p], i = 0; i < 3; ++i)
ans += recursive_solution(p,k+a*multiplier[i]);
return ans; };
const function<int(int,int)> brute_force_solution = [&](int n, int k) {
int ans = 0;
for (int U = pow3[n], s = 0; s < U; ++s) {
int sum = 0;
for (int x = s, i = 0; i < n; ++i, x /= 3)
sum += arr[i]*multiplier[x%3];
if (sum == k)
++ans; }
return ans; };
const auto submit = [&]() {
int T; cin.tie(nullptr)->sync_with_stdio(false), cin >> T;
for (int N, K, i; T--; cout << recursive_solution(N,K) << '\n')
for (cin >> N >> K, i = 0; i < N; ++i)
cin >> arr[i]; };
const auto test = [&]() {
random_device device;
mt19937_64 random(device());
uniform_int_distribution<int> uniform_N(1,P);
uniform_int_distribution<int> uniform_K(1,M);
uniform_int_distribution<int> uniform_A(-M,M);
int T; cin >> T;
int tests = 0;
while (T--) {
const int N = uniform_N(random), K = uniform_K(random);
for (int i = 0; i < N; ++i)
arr[i] = uniform_A(random);
const int rc_ans = recursive_solution(N,K);
const int bf_ans = brute_force_solution(N,K);
if (++tests%100 == 0)
cout << tests << " tests" << endl;
if (rc_ans != bf_ans) {
cout << "Generated test" << endl;
cout << 1 << endl << N << ' ' << K << endl << arr[0];
for (int i = 1; i < N; ++i)
cout << ' ' << arr[i];
cout << endl;
cout << "RC ans = " << rc_ans << endl;
cout << "BF ans = " << bf_ans << endl;
return; } } };
if (do_test)
test();
else
submit();
return 0; }
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKICAgIHVzaW5nIGl2ZWN0b3IgPSB2ZWN0b3I8aW50PjsKICAgIHVzaW5nIGltYXRyaXggPSB2ZWN0b3I8aXZlY3Rvcj47CiAgICBjb25zdCBpbnQgTSA9IDEwMCwgUCA9IDEwOwogICAgY29uc3QgaXZlY3RvciBtdWx0aXBsaWVyID0gey0xLDAsMX07CiAgICBjb25zdCBib29sIGRvX3Rlc3QgPSB0cnVlOwogICAgaXZlY3RvciBhcnIoUCksIHBvdzMoUCsxLDEpOwogICAgZm9yIChpbnQgeCA9IDE7IHggPD0gUDsgKyt4KQogICAgICAgIHBvdzNbeF0gPSAzKnBvdzNbeC0xXTsKICAgIGNvbnN0IGZ1bmN0aW9uPGludChpbnQsaW50KT4gcmVjdXJzaXZlX3NvbHV0aW9uID0gWyZdKGludCBuLCBpbnQgaykgewogICAgICAgIGlmIChuID09IDApCiAgICAgICAgICAgIHJldHVybiBpbnQoayA9PSAwKTsKICAgICAgICBpbnQgYW5zID0gMDsKICAgICAgICBmb3IgKGludCBwID0gbi0xLCBhID0gYXJyW3BdLCBpID0gMDsgaSA8IDM7ICsraSkKICAgICAgICAgICAgYW5zICs9IHJlY3Vyc2l2ZV9zb2x1dGlvbihwLGsrYSptdWx0aXBsaWVyW2ldKTsKICAgICAgICByZXR1cm4gYW5zOyB9OwogICAgY29uc3QgZnVuY3Rpb248aW50KGludCxpbnQpPiBicnV0ZV9mb3JjZV9zb2x1dGlvbiA9IFsmXShpbnQgbiwgaW50IGspIHsKICAgICAgICBpbnQgYW5zID0gMDsKICAgICAgICBmb3IgKGludCBVID0gcG93M1tuXSwgcyA9IDA7IHMgPCBVOyArK3MpIHsKICAgICAgICAgICAgaW50IHN1bSA9IDA7CiAgICAgICAgICAgIGZvciAoaW50IHggPSBzLCBpID0gMDsgaSA8IG47ICsraSwgeCAvPSAzKQogICAgICAgICAgICAgICAgc3VtICs9IGFycltpXSptdWx0aXBsaWVyW3glM107CiAgICAgICAgICAgIGlmIChzdW0gPT0gaykKICAgICAgICAgICAgICAgICsrYW5zOyB9CiAgICAgICAgcmV0dXJuIGFuczsgfTsKICAgIGNvbnN0IGF1dG8gc3VibWl0ID0gWyZdKCkgewogICAgICAgIGludCBUOyBjaW4udGllKG51bGxwdHIpLT5zeW5jX3dpdGhfc3RkaW8oZmFsc2UpLCBjaW4gPj4gVDsKICAgICAgICBmb3IgKGludCBOLCBLLCBpOyBULS07IGNvdXQgPDwgcmVjdXJzaXZlX3NvbHV0aW9uKE4sSykgPDwgJ1xuJykKICAgICAgICAgICAgZm9yIChjaW4gPj4gTiA+PiBLLCBpID0gMDsgaSA8IE47ICsraSkKICAgICAgICAgICAgICAgIGNpbiA+PiBhcnJbaV07IH07CiAgICBjb25zdCBhdXRvIHRlc3QgPSBbJl0oKSB7CiAgICAgICAgcmFuZG9tX2RldmljZSBkZXZpY2U7CiAgICAgICAgbXQxOTkzN182NCByYW5kb20oZGV2aWNlKCkpOwogICAgICAgIHVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxpbnQ+IHVuaWZvcm1fTigxLFApOwogICAgICAgIHVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxpbnQ+IHVuaWZvcm1fSygxLE0pOwogICAgICAgIHVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxpbnQ+IHVuaWZvcm1fQSgtTSxNKTsKICAgICAgICBpbnQgVDsgY2luID4+IFQ7CiAgICAgICAgaW50IHRlc3RzID0gMDsKICAgICAgICB3aGlsZSAoVC0tKSB7CiAgICAgICAgICAgIGNvbnN0IGludCBOID0gdW5pZm9ybV9OKHJhbmRvbSksIEsgPSB1bmlmb3JtX0socmFuZG9tKTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyArK2kpCiAgICAgICAgICAgICAgICBhcnJbaV0gPSB1bmlmb3JtX0EocmFuZG9tKTsKICAgICAgICAgICAgY29uc3QgaW50IHJjX2FucyA9IHJlY3Vyc2l2ZV9zb2x1dGlvbihOLEspOwogICAgICAgICAgICBjb25zdCBpbnQgYmZfYW5zID0gYnJ1dGVfZm9yY2Vfc29sdXRpb24oTixLKTsKICAgICAgICAgICAgaWYgKCsrdGVzdHMlMTAwID09IDApCiAgICAgICAgICAgICAgICBjb3V0IDw8IHRlc3RzIDw8ICIgdGVzdHMiIDw8IGVuZGw7CiAgICAgICAgICAgIGlmIChyY19hbnMgIT0gYmZfYW5zKSB7CiAgICAgICAgICAgICAgICBjb3V0IDw8ICJHZW5lcmF0ZWQgdGVzdCIgPDwgZW5kbDsKICAgICAgICAgICAgICAgIGNvdXQgPDwgMSA8PCBlbmRsIDw8IE4gPDwgJyAnIDw8IEsgPDwgZW5kbCA8PCBhcnJbMF07CiAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8IE47ICsraSkKICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICcgJyA8PCBhcnJbaV07CiAgICAgICAgICAgICAgICBjb3V0IDw8IGVuZGw7CiAgICAgICAgICAgICAgICBjb3V0IDw8ICJSQyBhbnMgPSAiIDw8IHJjX2FucyA8PCBlbmRsOwogICAgICAgICAgICAgICAgY291dCA8PCAiQkYgYW5zID0gIiA8PCBiZl9hbnMgPDwgZW5kbDsKICAgICAgICAgICAgICAgIHJldHVybjsgfSB9IH07CiAgICBpZiAoZG9fdGVzdCkKICAgICAgICB0ZXN0KCk7CiAgICBlbHNlIAogICAgICAgIHN1Ym1pdCgpOwogICAgcmV0dXJuIDA7IH0K