#ifdef LOCAL
#else
#include "biscuits.h"
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
#ifdef LOCAL
bool build(vector<vector<int>> p) {
return true;
}
#else
#endif
typedef __uint128_t int128;
ll count_tastiness(ll x, vector<ll> a) {
int it = 0;
while (it < a.size()) {
if (a[it] > x) {
if (it == a.size() - 1) {
a.push_back((a[it] - x) / 2);
} else {
a[it + 1] += (a[it] - x) / 2;
}
a[it] -= (a[it] - x) / 2 * 2;
}
it++;
}
int n = a.size();
vector<int128> po(n + 1);
for (int i = 0; i <= n; i++) {
if (i == 0) {
po[i] = 1;
} else {
po[i] = po[i - 1] * 2;
}
}
// cout << a << '\n';
if (x == 1) {
vector<ll> dp(n + 1, 0);
ll ans = 1;
int it1 = 0;
int it2 = 0;
while (it1 != n) {
if (a[it1] == 0) {
it2 = ++it1;
continue;
}
while (it2 != n - 1 && a[it2 + 1]) {
it2++;
}
ll cur = 1;
ll res = 0;
for (int i = it1; i <= it2; i++) {
if (a[i] == 1) {
cur *= 2;
} else {
res += cur;
cur *= 2;
}
}
res += cur;
ans *= res;
it1 = ++it2;
}
return ans;
}
/**
so therefore they're all <= x+1
dp[which level we've completed]
special property that you can only completely complete
level above
so if we go up
they can end a level, and
consecutive usage
*/
vector<int> go(n + 1, -1); // where to go to to complete
ll ans = 0;
for (int i = n - 1; i >= 0; i--) {
// how far you have to go to complete the layer i
if (a[i] == x) {
go[i] = i;
continue;
}
int128 num = 0;
int128 rem = 0;
for (int j = i; j >= 0; j--) {
int128 tot = a[j] * po[j];
num += (tot / po[i]);
rem += (tot % po[i]);
if (rem >= po[i]) {
rem -= po[i];
num += 1;
}
if (num >= x) {
go[i] = j;
break;
}
}
}
vector<ll> dp(n + 1); // you're done with layer i
dp[n] = 1; // you have nothing
for (int i = n; i >= 1; i--) {
// fill in layer i-1
if (go[i - 1] != -1) {
dp[go[i - 1]] += dp[i];
}
// do nothing
dp[i - 1] += dp[i];
}
return dp[0];
}
#ifdef LOCAL
int main() {
// ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("file.in", "r", stdin);
int q;
cin >> q;
for (int qq = 0; qq < q; qq++) {
ll k, x;
cin >> k >> x;
vector<ll> a(k);
for (int i = 0; i < k; i++) {
cin >> a[i];
}
cout << "TEST " << qq + 1 << ": "<< count_tastiness(x, a) << '\n';
}
return 0;
}
#else
#endif
