#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define FOR(i, x, n) for(ll i = x; i < n; i++)
#define pb push_back
#define pf push_front
#define ll long long
#define hii cout << "hii" << endl
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int ll
#define mpp make_pair
#define endl '\n'
#define ff first
#define ss second
#define vi vector<int>
#define all(s) s.begin(), s.end()
#define si size()
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
template <class Arg1, class... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
const char* sep = strchr(names + 1, ',');
cerr.write(names, sep - names) << " : " << arg1 << " ";
__f(sep + 1, args...);
}
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE
typedef
tree<
pair<int,int>,
null_type,
less<pair<int,int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
const int N = 1 << 12;
const int mod = 1e9 + 7;
int query = 1;
vector<pii> s1, s2;
int arr[22];
int brr[22];
int n, h;
void print(int ret)
{
cout << "Case #" << query++ << ": " << ret << endl;
}
void f(int idx, int cnt1, int cnt2)
{
if(idx == n / 2)
{
s1.push_back({cnt1,cnt2});
return;
}
f(idx + 1, cnt1 + arr[idx], cnt2);
f(idx + 1, cnt1, cnt2 + brr[idx]);
f(idx + 1, cnt1 + arr[idx], cnt2 + brr[idx]);
}
void g(int idx, int cnt1, int cnt2)
{
if(idx == n)
{
s2.push_back({cnt1,cnt2});
return;
}
g(idx + 1, cnt1 + arr[idx], cnt2);
g(idx + 1, cnt1, cnt2 + brr[idx]);
g(idx + 1, cnt1 + arr[idx], cnt2 + brr[idx]);
}
void solve()
{
s1.clear();
s2.clear();
cin >> n >> h;
for(int i = 0; i < n; i++)
{
cin >> arr[i];
}
for(int i = 0; i < n; i++)
{
cin >> brr[i];
}
f(0, 0, 0);
g(n / 2, 0, 0);
int n = s1.size(), m = s2.size();
sort(all(s1));
sort(all(s2));
int j = m - 1;
int ret = 0;
ordered_set os;
int el = 0;
int sz = 0;
for(int i = 0; i < n; i++)
{
// for(int j = 0; j < m; j++)
// {
// if(s1[i].first + s2[j].first)
// {
// }
// }
while(j >= 0 and s1[i].first + s2[j].first >= h)
{
el++;
os.insert({s2[j].second, sz++});
// mp[s2[j].second]++;
j--;
}
int ptr2 = j + 1;
if(ptr2 == m)
{
continue;
}
if(s1[i].second >= h)
{
ret += el;
continue;
}
int x = h - s1[i].second;
int kitnebadey = os.size() - os.order_of_key({x, 0});
ret += kitnebadey;
}
print(ret);
}
int32_t main()
{
ios_base:: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
int t = 1;
cin >> t;
while(t--)solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiAKdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKIAojZGVmaW5lIEZPUihpLCB4LCBuKSBmb3IobGwgaSA9IHg7IGkgPCBuOyBpKyspIAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIHBmIHB1c2hfZnJvbnQKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBoaWkgY291dCA8PCAiaGlpIiA8PCBlbmRsCiNkZWZpbmUgcGlpIHBhaXI8aW50LCBpbnQ+CiNkZWZpbmUgcGxsIHBhaXI8bGwsIGxsPgojZGVmaW5lIGludCBsbAojZGVmaW5lIG1wcCBtYWtlX3BhaXIKI2RlZmluZSBlbmRsICdcbicKI2RlZmluZSBmZiBmaXJzdCAKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIGFsbChzKSBzLmJlZ2luKCksIHMuZW5kKCkKI2RlZmluZSBzaSBzaXplKCkKIAp0ZW1wbGF0ZSA8Y2xhc3MgVD4gb3N0cmVhbSYgb3BlcmF0b3IgPDwgKG9zdHJlYW0gJm9zLCBjb25zdCB2ZWN0b3I8VD4gJnYpIHsgZm9yIChUIGkgOiB2KSBvcyA8PCBpIDw8ICcgJzsgcmV0dXJuIG9zOyB9CnRlbXBsYXRlIDxjbGFzcyBUPiBvc3RyZWFtJiBvcGVyYXRvciA8PCAob3N0cmVhbSAmb3MsIGNvbnN0IHNldDxUPiAmdikgeyBmb3IgKFQgaSA6IHYpIG9zIDw8IGkgPDwgJyAnOyByZXR1cm4gb3M7IH0KdGVtcGxhdGUgPGNsYXNzIFQsIGNsYXNzIFM+IG9zdHJlYW0mIG9wZXJhdG9yIDw8IChvc3RyZWFtICZvcywgY29uc3QgcGFpcjxULCBTPiAmdikgeyBvcyA8PCB2LmZpcnN0IDw8ICcgJyA8PCB2LnNlY29uZDsgcmV0dXJuIG9zOyB9CnRlbXBsYXRlIDxjbGFzcyBULCBjbGFzcyBTPiBvc3RyZWFtJiBvcGVyYXRvciA8PCAob3N0cmVhbSAmb3MsIGNvbnN0IHVub3JkZXJlZF9tYXA8VCwgUz4gJnYpIHsgZm9yIChhdXRvIGkgOiB2KSBvcyA8PCAnKCcgPDwgaS5maXJzdCA8PCAiPT4iIDw8IGkuc2Vjb25kIDw8ICcpJyA8PCAnICc7IHJldHVybiBvczsgfSAKIAogCiNpZm5kZWYgT05MSU5FX0pVREdFCiNkZWZpbmUgdHJhY2UoLi4uKSBfX2YoI19fVkFfQVJHU19fLCBfX1ZBX0FSR1NfXykKICAgIHRlbXBsYXRlIDxjbGFzcyBBcmcxPiB2b2lkIF9fZihjb25zdCBjaGFyKiBuYW1lLCBBcmcxJiYgYXJnMSkgeyBjZXJyIDw8IG5hbWUgPDwgIiA6ICIgPDwgYXJnMSA8PCBlbmRsOyB9CiAgICB0ZW1wbGF0ZSA8Y2xhc3MgQXJnMSwgY2xhc3MuLi4gQXJncz4KICAgIHZvaWQgX19mKGNvbnN0IGNoYXIqIG5hbWVzLCBBcmcxJiYgYXJnMSwgQXJncyYmLi4uIGFyZ3MpIHsKICAgICAgICBjb25zdCBjaGFyKiBzZXAgPSBzdHJjaHIobmFtZXMgKyAxLCAnLCcpOwogICAgICAgIGNlcnIud3JpdGUobmFtZXMsIHNlcCAtIG5hbWVzKSA8PCAiIDogIiA8PCBhcmcxIDw8ICIgICI7CiAgICAgICAgX19mKHNlcCArIDEsIGFyZ3MuLi4pOwogICAgfQojZWxzZQojZGVmaW5lIHRyYWNlKC4uLikgMAojcHJhZ21hIEdDQyBvcHRpbWl6ZSAoIk8zIikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJ1bnJvbGwtbG9vcHMiKQojcHJhZ21hIEdDQyB0YXJnZXQoImF2eDIsc3NlLHNzZTIsc3NlMyxzc3NlMyxzc2U0LHBvcGNudCxhYm0sbW14LGF2eCx0dW5lPW5hdGl2ZSIpCiNkZWZpbmUgX0NSVF9TRUNVUkVfTk9fV0FSTklOR1MKI2VuZGlmIC8vIGlmbmRlZiBPTkxJTkVfSlVER0UKCgp0eXBlZGVmCnRyZWU8CiAgcGFpcjxpbnQsaW50PiwKICBudWxsX3R5cGUsCiAgbGVzczxwYWlyPGludCxpbnQ+PiwKICByYl90cmVlX3RhZywKICB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+Cm9yZGVyZWRfc2V0OwogCiAKY29uc3QgaW50IE4gPSAxIDw8IDEyOwpjb25zdCBpbnQgbW9kID0gMWU5ICsgNzsKaW50IHF1ZXJ5ID0gMTsKdmVjdG9yPHBpaT4gczEsIHMyOwppbnQgYXJyWzIyXTsKaW50IGJyclsyMl07CmludCBuLCBoOwp2b2lkIHByaW50KGludCByZXQpCnsKICAgIGNvdXQgPDwgIkNhc2UgIyIgPDwgcXVlcnkrKyA8PCAiOiAiIDw8IHJldCA8PCBlbmRsOwp9CgoKCnZvaWQgZihpbnQgaWR4LCBpbnQgY250MSwgaW50IGNudDIpCnsKCWlmKGlkeCA9PSBuIC8gMikKCXsKCQlzMS5wdXNoX2JhY2soe2NudDEsY250Mn0pOwoJCXJldHVybjsKCX0KCWYoaWR4ICsgMSwgY250MSArIGFycltpZHhdLCBjbnQyKTsKCWYoaWR4ICsgMSwgY250MSwgY250MiArIGJycltpZHhdKTsKICAgIGYoaWR4ICsgMSwgY250MSArIGFycltpZHhdLCBjbnQyICsgYnJyW2lkeF0pOwp9CnZvaWQgZyhpbnQgaWR4LCBpbnQgY250MSwgaW50IGNudDIpCnsKCWlmKGlkeCA9PSBuKQoJewoJCXMyLnB1c2hfYmFjayh7Y250MSxjbnQyfSk7CgkJcmV0dXJuOwoJfQoJZyhpZHggKyAxLCBjbnQxICsgYXJyW2lkeF0sIGNudDIpOwoJZyhpZHggKyAxLCBjbnQxLCBjbnQyICsgYnJyW2lkeF0pOwogICAgZyhpZHggKyAxLCBjbnQxICsgYXJyW2lkeF0sIGNudDIgKyBicnJbaWR4XSk7Cn0KCnZvaWQgc29sdmUoKQp7CglzMS5jbGVhcigpOwoJczIuY2xlYXIoKTsKCWNpbiA+PiBuID4+IGg7Cglmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJewoJCWNpbiA+PiBhcnJbaV07Cgl9Cglmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJewoJCWNpbiA+PiBicnJbaV07Cgl9CglmKDAsIDAsIDApOwoJZyhuIC8gMiwgMCwgMCk7CglpbnQgbiA9IHMxLnNpemUoKSwgbSA9IHMyLnNpemUoKTsKCXNvcnQoYWxsKHMxKSk7Cglzb3J0KGFsbChzMikpOwoJaW50IGogPSBtIC0gMTsKCWludCByZXQgPSAwOwoJb3JkZXJlZF9zZXQgb3M7CglpbnQgZWwgPSAwOwoJaW50IHN6ID0gMDsKCWZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgl7CgkJLy8gZm9yKGludCBqID0gMDsgaiA8IG07IGorKykKCQkvLyB7CgkJLy8gCWlmKHMxW2ldLmZpcnN0ICsgczJbal0uZmlyc3QpCgkJLy8gCXsKCgkJLy8gCX0KCQkvLyB9CgkJd2hpbGUoaiA+PSAwIGFuZCBzMVtpXS5maXJzdCArIHMyW2pdLmZpcnN0ID49IGgpCgkJewoJCQllbCsrOwoJCQlvcy5pbnNlcnQoe3MyW2pdLnNlY29uZCwgc3orK30pOwoJCQkvLyBtcFtzMltqXS5zZWNvbmRdKys7CgkJCWotLTsKCQl9CgkJaW50IHB0cjIgPSBqICsgMTsKCQlpZihwdHIyID09IG0pCgkJewoJCQljb250aW51ZTsKCQl9CgkJaWYoczFbaV0uc2Vjb25kID49IGgpCgkJewoJCQlyZXQgKz0gZWw7CgkJCWNvbnRpbnVlOwoJCX0KCQlpbnQgeCA9IGggLSBzMVtpXS5zZWNvbmQ7CgkJaW50IGtpdG5lYmFkZXkgPSBvcy5zaXplKCkgLSBvcy5vcmRlcl9vZl9rZXkoe3gsIDB9KTsKCQlyZXQgKz0ga2l0bmViYWRleTsKCX0KCXByaW50KHJldCk7Cn0KIAogCmludDMyX3QgbWFpbigpCnsJCiAgICBpb3NfYmFzZTo6IHN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4udGllKE5VTEwpOwoJY291dC50aWUoTlVMTCk7Ci8vIAkjaWZuZGVmIE9OTElORV9KVURHRQovLyAJICAgIGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwovLyAJICAgIGZyZW9wZW4oIm91dHB1dC50eHQiLCAidyIsIHN0ZG91dCk7Ci8vIAkjZW5kaWYKCWludCB0ID0gMTsKCWNpbiA+PiB0OwoJd2hpbGUodC0tKXNvbHZlKCk7CglyZXR1cm4gMDsKfQog