#include "bits/stdc++.h"
using namespace std;

using i64 = long long;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<double> a(n);
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            a[i] = x;
        }
        double left = 0, right = *max_element(a.begin(), a.end());
        vector<int> s(n);
        for (int iter = 0; iter < 100; iter++) {
            double mid = (left + right) / 2;
            bool ok = true;
            for (int i = 0; i < n; i++) {
                if (mid >= a[i]) {
                    s[i] = 0;
                } else {
                    double ratio = a[i] / mid;
                    s[i] = ceil(log2(ratio));
                }
            }
            for (int i = 1; i < n; i++) {
                if (s[i] < s[i-1]) {
                    s[i] = s[i-1];
                }
            }
            int total = 0;
            for (int i = 0; i < n; i++) {
                total += s[i];
                if (total > k) break;
            }
            if (total <= k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        double max_val = 0;
        vector<int> s_final(n);
        for (int i = 0; i < n; i++) {
            if (right >= a[i]) {
                s_final[i] = 0;
            } else {
                double ratio = a[i] / right;
                s_final[i] = ceil(log2(ratio));
            }
        }
        for (int i = 1; i < n; i++) {
            if (s_final[i] < s_final[i-1]) {
                s_final[i] = s_final[i-1];
            }
        }
        for (int i = 0; i < n; i++) {
            double val = a[i] / (1LL << s_final[i]);
            max_val = max(max_val, val);
        }
        i64 numerator = 0;
        int exponent = 0;
        while (exponent <= 60) {
            i64 candidate = round(max_val * (1LL << exponent));
            if (abs(candidate / (double)(1LL << exponent) - max_val) < 1e-9) {
                numerator = candidate;
                break;
            }
            exponent++;
        }
        while (exponent > 0 && (numerator % 2) == 0) {
            numerator /= 2;
            exponent--;
        }
        string s_bin;
        if (numerator == 0) {
            s_bin = "0";
        } else {
            while (numerator) {
                s_bin += (numerator % 2) + '0';
                numerator /= 2;
            }
            reverse(s_bin.begin(), s_bin.end());
        }
        cout << s_bin << '\n';
    }
}