#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long dp[35][4][4];

void precompute() {
    for (int u = 0; u < 4; ++u) {
        for (int v = 0; v < 4; ++v) {
            dp[0][u][v] = (u == 2) + (v == 2);
        }
    }
    for (int i = 0; i < 30; ++i) {
        for (int u = 0; u < 4; ++u) {
            for (int v = 0; v < 4; ++v) {
                int mid = u ^ v;
                dp[i+1][u][v] = dp[i][u][mid] + dp[i][mid][v] - (mid == 2);
            }
        }
    }
}

void print128(__int128 n) {
    if (n == 0) {
        cout << 0 << "\n";
        return;
    }
    string s;
    while (n > 0) {
        s += (char)('0' + (n % 10));
        n /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s << "\n";
}

void solve() {
    int n, k;
    cin >> n >> k;
    string s, z;
    cin >> s >> z;
    
    long long cnt[4] = {0};
    for (int i = 0; i < n; ++i) {
        int tp = ((s[i] - '0') << 1) | (z[i] - '0');
        cnt[tp]++;
    }
    
    __int128 total_sum = 0;
    for (int tp = 0; tp < 4; ++tp) {
        for (int tq = 0; tq < 4; ++tq) {
            long long pairs = cnt[tp] * cnt[tq];
            if (pairs == 0) continue;
            int sL = ((tp >> 1) << 1) | (tq >> 1);
            int sR = ((tp & 1) << 1) | (tq & 1);
            total_sum += (__int128)pairs * dp[k][sL][sR];
        }
    }
    print128(total_sum);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}