#include <bits/stdc++.h>

#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size) memset(array, value, ((size) + 5) * sizeof(decltype(array[0])))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v) (sort(vecall(v), greater<decltype(v.back())>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
#define vecunique(v) ((v).resize(unique(vecall(v))-(v).begin())
using namespace std;
using db = long double;
const int N = 1000050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const db PI = acos(-1.0L);
#define MULTIPLE_CASE
#define CLOSE_IOS

int add(int a, int b) { return (a + b) >= mod ? a + b - mod : a + b; }

int sub(int a, int b) { return (a - b) < 0 ? a - b + mod : a - b; }

int mul(long long a, long long b) { return add(a * b % mod, mod); }

const int M = 2;

struct mat {
    int a[M][M]{};

    mat() { memset(a, 0, sizeof(a)); }
};

mat operator*(const mat &A, const mat &B) {
    mat ret;
    for (int i = 0; i < M; ++i)
        for (int j = 0; j < M; ++j)
            for (int k = 0; k < M; ++k)
                ret.a[i][j] = add(ret.a[i][j], mul(A.a[i][k], B.a[k][j]));
    return ret;
}

mat ksm(mat a, int b) {
    mat ret;
    for (int i = 0; i < M; ++i)ret.a[i][i] = 1;
    while (b) {
        if (b & 1)ret = ret * a;
        a = a * a, (b >>= 1);
    }
    return ret;
}

int n, m;
pii s[N];
map<int, int> segs;

int cal1(int len) {
    mat mat_xi;
    mat_xi.a[0][0] = 3, mat_xi.a[0][1] = mod - 1, mat_xi.a[1][0] = 1;
    if (len > 1) {
        mat_xi = ksm(mat_xi, len - 1);
        int res = add(mat_xi.a[0][1], mul(mat_xi.a[0][0], 3));
        return res;
    } else {
        return len == 0 ? 1 : 3;
    }
}

int cal2(int len) {
    mat mat_xi;
    mat_xi.a[0][0] = 1, mat_xi.a[0][1] = 1;
    mat_xi.a[1][0] = 1;
    if (len > 2) {
        mat_xi = ksm(mat_xi, 2 * len - 1);
        int res = add(mat_xi.a[0][0], mul(mat_xi.a[0][1], 1));
        return sub(res, 1);
    } else {
        if (len == 0) return 1;
        if (len == 1) return 4;
        else return 12;
    }
}

void work() {
    int ans = cal1(s[1].first - 1);
    ans = mul(ans, cal1(n - s[m].second));
    for (int i = 1; i < m; ++i) {
        int l = s[i].second, r = s[i + 1].first;
        int res = cal2(r - l - 1);
        ans = mul(ans, add(res, 1));
    }
    cout << ans << "\n";
}

inline void solve() {
    cin >> n >> m;
    segs.clear();
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        segs[x]++, segs[y]--;
    }
    m = 0;
    int cnt = 0;
    for (auto &[pos, c]: segs) {
        if (cnt == 0 && c > 0)
            s[++m].first = pos;
        else if (cnt + c == 0) {
            if (cnt == 0) ++m, s[m].first = pos;
            s[m].second = pos;
        }
        cnt += c;
    }
    assert(m != 0);
    work();
}

int main() {
#ifdef CLOSE_IOS
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#endif
    int Test = 1;
#ifdef MULTIPLE_CASE
#ifdef CLOSE_IOS
    cin >> Test;
#else
    scanf("%d", &Test);
#endif
#endif
    while (Test--) {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    return 0;
}