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

using ll = long long;

ll dp[32][2][2][2][2];

void precompute() {
    for (int k = 0; k <= 30; k++)
        for (int b1 = 0; b1 < 2; b1++)
            for (int b2 = 0; b2 < 2; b2++)
                for (int c1 = 0; c1 < 2; c1++)
                    for (int c2 = 0; c2 < 2; c2++)
                        if (k == 0) dp[k][b1][b2][c1][c2] = (b1 == 1 && c1 == 1) + (b2 == 1 && c2 == 1);
                        else {
                            int mid_b = b1 ^ b2, mid_c = c1 ^ c2;
                            ll L = dp[k - 1][b1][mid_b][c1][mid_c], R = dp[k - 1][mid_b][b2][mid_c][c2];
                            dp[k][b1][b2][c1][c2] = L + R;
                            if (mid_b == 1 && mid_c == 1) dp[k][b1][b2][c1][c2]--;
                        }
}

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

    ll F[2][2] = {0};
    for (int i = 0; i < n; i++) {
        int b1 = s[i] - '0', b2 = z[i] - '0';
        F[b1][b2]++;
    }

    ll sum = 0, sum2 = 0;
    for (int b1 = 0; b1 < 2; b1++)
        for (int b2 = 0; b2 < 2; b2++) {
            if (F[b1][b2] == 0) continue;
            sum += F[b1][b2] * dp[k][b1][b2][b1][b2];
            for (int c1 = 0; c1 < 2; c1++)
                for (int c2 = 0; c2 < 2; c2++) {
                    if (F[c1][c2] == 0) continue;
                    sum2 += F[b1][b2] * F[c1][c2] * dp[k][b1][b2][c1][c2];
                }
        }
    ll ans = n * sum - sum2;
    cout << ans << '\n';
}

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

    precompute();

    int tests = 1; cin >> tests;
    while (tests--) solve();
    
    return 0;
}