#include <bits/stdc++.h>
#include <cassert>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
#define int ll

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
void shuf(vector<T>& a) {
    for (int i = 1; i < sz(a); i++) swap(a[i], a[rnd() % (i + 1)]);
}

struct WW {
    set<pair<int, int>> st;
    set<pair<int, int>>::iterator it;
    int sm = 0, siz = 0;
    WW() = default;
    void add(pair<int, int> x, pair<int, int> y) {
        if (st.empty()) {
            st.insert(x); st.insert(y); it = st.begin();
            sm = abs(x.second - y.second);
            siz += 2;
            return;
        }

        if (min(x, y) < *it && max(x, y) > *it) {
            sm +=max(x, y).second- min(x, y).second;
            pair<int, int> val = *it;
            st.insert(x); st.insert(y); it = st.find(val);
        } else if (min(x, y) > *it) {
            sm += x.second + y.second - 2 * (*it).second;
            pair<int, int> val = *it;
            st.insert(x); st.insert(y); it = st.find(val);
            it++;
            int dlt = (*it).second - val.second;
            sm -= 2 * dlt;
        } else {
            sm += 2 * (*it).second - x.second - y.second;
            pair<int, int> val = *it;
            st.insert(x); st.insert(y); it = st.find(val);
            it--;
        }
        siz += 2;
    }
};

void solve() {
    int k, n; cin >> k >> n;
    vector<pair<int, int>> lol;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        char r1, r2;
        int p1, p2;
        cin >> r1 >> p1 >> r2 >> p2;
        if (r1 == r2) {
            ans += abs(p1 - p2);
            continue;
        }
        ans++;
        lol.pb({p1, p2});
    }
    if (k == 1) {
        vector<int> ap;
        for (auto u : lol) {
            ap.pb(u.first); ap.pb(u.second);
        }
        sort(all(ap));
        if (!ap.empty()) {
            int mp = ap[sz(ap) / 2];
            for (int j = 0; j < sz(ap); j++) ans += abs(ap[j] - mp);
        }
        cout << ans << '\n';
        return;
    }
    sort(all(lol), [&](pair<int, int> x, pair<int, int> y) {
        return x.first + x.second < y.first + y.second;
    });
    vector<pair<int, int>> pp;
    for (int i = 0; i < sz(lol); i++) {
        pp.pb({lol[i].first, 2 * i}); pp.pb({lol[i].second, 2 * i + 1});
    }
    sort(all(pp));
    vector<array<int, 2>> pos(sz(lol));
    for (int i = 0; i < sz(pp); i++) {
        pos[pp[i].second / 2][pp[i].second % 2] = i;
    }
    vector<int> cp(sz(lol) + 1), cs(sz(lol) + 1);
    WW pr, sf;
    for (int j = 0; j < sz(lol); j++) {
        pr.add({pos[j][0], lol[j].first}, {pos[j][1], lol[j].second});
        cp[j + 1] = pr.sm;
    }
    for (int j = sz(lol) - 1; j >= 0; j--) {
        sf.add({pos[j][0], lol[j].first}, {pos[j][1], lol[j].second});
        cs[sz(lol) - j] = sf.sm;
    }
    int dop = 1e18;
    for (int ppp = 0; ppp <= sz(lol); ppp++) dop = min(dop, cp[ppp] + cs[sz(lol) - ppp]);
    cout << ans + dop << '\n';
}   

signed main() {
    int tt = 1;
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false);
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}