Fuzzy Concatenation (Hard version)

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

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct SuffixArray {
    vector<int> a, sa, rank_pos, lcp, lg;
    vector<vector<int>> st;

    void build(const vector<int>& v) {
        a = v;
        a.push_back(0);
        int n = (int)a.size();

        sa.assign(n, 0);
        rank_pos.assign(n, 0);

        int alphabet = max(30, n + 1);
        vector<int> cnt(alphabet, 0);
        for (int x : a) cnt[x]++;
        for (int i = 1; i < alphabet; i++) cnt[i] += cnt[i - 1];
        for (int i = 0; i < n; i++) sa[--cnt[a[i]]] = i;

        int classes = 1;
        rank_pos[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            if (a[sa[i]] != a[sa[i - 1]]) classes++;
            rank_pos[sa[i]] = classes - 1;
        }

        vector<int> sa2(n), rank2(n);
        for (int h = 0; (1 << h) < n; h++) {
            int shift = 1 << h;
            for (int i = 0; i < n; i++) {
                sa2[i] = sa[i] - shift;
                if (sa2[i] < 0) sa2[i] += n;
            }

            cnt.assign(classes, 0);
            for (int x : rank_pos) cnt[x]++;

            vector<int> pos(classes, 0);
            for (int i = 1; i < classes; i++) pos[i] = pos[i - 1] + cnt[i - 1];
            for (int x : sa2) sa[pos[rank_pos[x]]++] = x;

            rank2[sa[0]] = 0;
            int new_classes = 1;
            for (int i = 1; i < n; i++) {
                pair<int, int> cur = {rank_pos[sa[i]], rank_pos[(sa[i] + shift) % n]};
                pair<int, int> prv = {rank_pos[sa[i - 1]], rank_pos[(sa[i - 1] + shift) % n]};
                if (cur != prv) new_classes++;
                rank2[sa[i]] = new_classes - 1;
            }
            rank_pos.swap(rank2);
            classes = new_classes;
        }

        for (int i = 0; i < n; i++) rank_pos[sa[i]] = i;
        build_lcp();
    }

    void build_lcp() {
        int n = (int)a.size();
        lcp.assign(max(0, n - 1), 0);

        int k = 0;
        for (int i = 0; i < n; i++) {
            int r = rank_pos[i];
            if (r == n - 1) {
                k = 0;
                continue;
            }
            int j = sa[r + 1];
            while (i + k < n && j + k < n && a[i + k] == a[j + k]) k++;
            lcp[r] = k;
            if (k) k--;
        }

        int len = (int)lcp.size();
        lg.assign(len + 1, 0);
        for (int i = 2; i <= len; i++) lg[i] = lg[i / 2] + 1;

        int levels = len ? lg[len] + 1 : 0;
        st.assign(levels, vector<int>(len));
        if (!len) return;

        st[0] = lcp;
        for (int p = 1; p < levels; p++) {
            int step = 1 << p;
            int half = step >> 1;
            for (int i = 0; i + step <= len; i++) {
                st[p][i] = min(st[p - 1][i], st[p - 1][i + half]);
            }
        }
    }

    int get_lcp(int i, int j) const {
        if (i == j) return (int)a.size() - i;
        int x = rank_pos[i], y = rank_pos[j];
        if (x > y) swap(x, y);
        int len = y - x;
        int p = lg[len];
        return min(st[p][x], st[p][y - (1 << p)]);
    }
};

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

    vector<int> text;
    text.reserve(n + m + 1);
    for (char c : s) text.push_back(c - 'a' + 2);
    text.push_back(1);
    for (char c : t) text.push_back(c - 'a' + 2);

    SuffixArray suf;
    suf.build(text);

    vector<int> from_s;
    from_s.reserve(n);
    for (int pos : suf.sa) {
        if (pos < n) from_s.push_back(pos);
    }

    int t_base = n + 1;

    auto finish_compare = [](int x, int y, int len) -> pair<int, int> {
        if (x < y) return {1, len};
        return {-1, len};
    };

    auto compare_modified = [&](int s_pos, int start, int pos, int ch) -> pair<int, int> {
        int rel = pos - start;
        int t_pos = t_base + start;
        int first = suf.get_lcp(s_pos, t_pos);

        if (first < rel) {
            return finish_compare(suf.a[s_pos + first], suf.a[t_pos + first], first);
        }

        if (first > rel) {
            int source_char = suf.a[s_pos + rel];
            if (source_char != ch) {
                return finish_compare(source_char, ch, rel);
            }
            return finish_compare(suf.a[s_pos + first], suf.a[t_pos + first], first);
        }

        int source_char = suf.a[s_pos + rel];
        if (source_char != ch) {
            return finish_compare(source_char, ch, rel);
        }

        int second = suf.get_lcp(s_pos + rel + 1, t_pos + rel + 1);
        int len = rel + 1 + second;
        return finish_compare(suf.a[s_pos + len], suf.a[t_pos + len], len);
    };

    auto max_len_with_edit = [&](int start, int pos, int ch) {
        int lo = 0, hi = (int)from_s.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (compare_modified(from_s[mid], start, pos, ch).first == -1) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        int best = 0;
        if (lo > 0) best = max(best, compare_modified(from_s[lo - 1], start, pos, ch).second);
        if (lo < (int)from_s.size()) best = max(best, compare_modified(from_s[lo], start, pos, ch).second);
        return best;
    };

    int ans = 0;
    int start = 0;
    int best = -1;

    for (int i = 0; i < m; i++) {
        int here = 0;
        for (int ch = 2; ch < 28; ch++) {
            here = max(here, max_len_with_edit(start, i, ch));
        }

        best = max(best, here);
        if (here < i - start + 1) {
            ans++;
            start += best;
            best = -1;
            i = start - 1;
        }
    }

    if (start < m) ans++;
    cout << ans << '\n';
}

int main() {
    setIO();
    int tc;
    cin >> tc;
    while (tc--) solve();
}