#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

// Helper function to generate all possible subset sums with their minimal element counts
vector<pair<ll, int>> generate_subset_sums(const vi &subset) {
    unordered_map<ll, int> sum_map;
    sum_map[0] = 0; // Base case: sum 0 with 0 elements

    for(auto num : subset) {
        // To prevent using the same element multiple times, iterate over a snapshot
        unordered_map<ll, int> current = sum_map;
        for(auto &[sum, count] : current) {
            ll new_sum = sum + num;
            if(sum_map.find(new_sum) == sum_map.end() || count + 1 < sum_map[new_sum]) {
                sum_map[new_sum] = count + 1;
            }
        }
    }

    // Convert the map to a vector of pairs for easy processing
    vector<pair<ll, int>> subset_sums;
    subset_sums.reserve(sum_map.size());
    for(auto &[sum, count] : sum_map) {
        subset_sums.emplace_back(sum, count);
    }
    return subset_sums;
}

// Function to calculate minimum number of elements to reach sum k using Meet-in-the-Middle
int minElementsToSumK_MITM(const vi &arr, int k) {
    int n = arr.size();
    int mid = n / 2;

    // Split the array into two halves
    vi left_half(arr.begin(), arr.begin() + mid);
    vi right_half(arr.begin() + mid, arr.end());

    // Generate all possible subset sums for both halves
    vector<pair<ll, int>> sums_left = generate_subset_sums(left_half);
    vector<pair<ll, int>> sums_right = generate_subset_sums(right_half);

    // Sort sums_right based on the sum value to enable binary search
    sort(sums_right.begin(), sums_right.end(),
        [&](const pair<ll, int> &a, const pair<ll, int> &b) -> bool {
            return a.first < b.first;
        });

    // For sums_right, keep track of the minimal count for each sum
    // This helps in efficiently finding the minimal count during binary search
    unordered_map<ll, int> sum_right_map;
    for(auto &[sum, count] : sums_right) {
        if(sum_right_map.find(sum) == sum_right_map.end() || count < sum_right_map[sum]) {
            sum_right_map[sum] = count;
        }
    }

    // Sort sums_left for efficient traversal
    sort(sums_left.begin(), sums_left.end(),
        [&](const pair<ll, int> &a, const pair<ll, int> &b) -> bool {
            return a.first < b.first;
        });

    // Initialize the answer with a large number
    int min_count = INT32_MAX;

    // Iterate through all subset sums in the left half
    for(auto &[sum_left, count_left] : sums_left) {
        ll required = (ll)k - sum_left;

        // Binary search in sums_right for the complement sum
        // Alternatively, use the map for O(1) lookup
        if(sum_right_map.find(required) != sum_right_map.end()) {
            int combined_count = count_left + sum_right_map[required];
            if(combined_count < min_count) {
                min_count = combined_count;
            }
        }
    }

    // If the target sum k is achievable, return the minimal count; otherwise, return -1
    return (min_count != INT32_MAX) ? min_count : -1;
}

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    // Ensure that the input string has exactly n characters
    if(s.length() != n){
        // Handle error or adjust accordingly
        // For this example, we'll truncate or pad the string
        if(s.length() > n){
            s = s.substr(0, n);
        }
        else{
            while(s.length() < n){
                s += '0'; // Assuming padding with '0's
            }
        }
    }

    // Initialize vectors to store cumulative counts of '0's and '1's
    // v[i][0] = number of '0's up to and including index i
    // v[i][1] = number of '1's up to and including index i
    vector<vector<int>> v(n, vector<int>(2, 0));
    int a = 0, b = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '0') a++;
        else if(s[i] == '1') b++;
        // If the string contains characters other than '0' and '1', they are ignored
        v[i][0] = a;
        v[i][1] = b;
    }

    // Construct the array 'arr' based on the given logic
    vi arr(n);
    int bb = v[n-1][1]; // Total number of '1's
    int aa = v[n-1][0]; // Total number of '0's
    for(int i = 0; i < n; i++) {
        
        arr[i] = max(0,(bb - v[i][1]) - (aa - v[i][0]));
    }

    // Apply the Meet-in-the-Middle function to find the minimum number of elements to reach sum k
    int result = minElementsToSumK_MITM(arr, k);
    cout << result + (!(minElementsToSumK_MITM(arr, k)== -1)) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
} optimise this code, here the array contains only non negative elements