CF1

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int, int>
#define pb(x) push_back(x)
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v) {
    for (auto x : v) cout << x << ' ';
    cout << "\n";
}

void cvl(vector <ll> &v) {
    for (auto x : v) cout << x << ' ';
    cout << "\n";
}


void cvv(vector <vector <int> > &v) {
    for (auto x : v) cv(x);
    cout << "\n";
}

void cvb(vector <bool> v) {
    for (bool x : v) cout << x << ' ';
    cout << "\n";
}

void cvs(vector <string>  v) {
    for (auto a : v) {
        cout << a << "\n";
    }
}

void cvp(vector <pii> a) {
    for (auto p : a) {
        cout << p.first << ' ' << p.second << "\n";
    }
    cout << "\n";
}
bool see = 1;

int lcs(vector <char> a, vector <char> b) {
    int m = a.size();
    vector <vector <int> > v(m, vector <int> (m, 0));
    if (a[0] == b[0]) {
        for (int i = 0; i < m; ++i) {
            v[i][0] = 1;
            v[0][i] = 1;
        }
    } else if (a[1] == b[0]) {
        for (int i = 0; i < m; ++i) {
            v[1][i] = 1;
        }
        for (int i = 1; i < m; ++i) {
            v[i][0] = 1;
        }
    } else if (a[0] == b[1]) {
        for (int i = 0; i < m; ++i) {
            v[i][1] = 1;
        }
        for (int i = 1; i < m; ++i) {
            v[0][i] = 1;
        }
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < m; ++j) {
            if (a[i] == b[j]) {
                v[i][j] = v[i - 1][j - 1] + 1;
            }
            else if (v[i - 1][j] >= v[i][j - 1]) {
                v[i][j] = v[i - 1][j];
            }
            else {
                v[i][j] = v[i][j - 1];
            }
        }
    }
    if (see) {
        cout << "v\n";
        cvv(v);
    }
    return v[m - 1][m - 1];
}

void slv() {
    int n, q; cin >> n >> q;
    string a, b; cin >> a >> b;
    for (int k = 0; k < q; ++k) {
        int l, r; cin >> l >> r;
        l--; r--;
        vector <char> sa, sb;
        for (int i = l; i <= r; ++i) {
            sa.push_back(a[i]);
            sb.push_back(b[i]);
        }
        sort(sa.begin(), sa.end());
        sort(sb.begin(), sb.end());
        if (see) {
            cout << "l r " << l << ' ' << r << "\n";
            cout << "sa sb\n";
            for (char l: sa) cout << l;
            cout << "\n";
            for (char l: sb) cout << l;
            cout << "\n";
        }
        int cmn = lcs(sa, sb);
        int m = r - l + 1;
        int ans = m - cmn;
        cout << ans << "\n";
    }
}
/*
1
6 1
aaabbb
aabbba
1 5


1
6 1
uwuwuw
wuwuwu
1 3
*/

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t; cin >> t;
    for (int go = 0; go < t; ++go) {
        slv();
    }
}