#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define re register
#define N 120203
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int mod=998244353;
struct node{
	int a[3][3],n,m;
	void init(int x,int nn,int mm){
		n=nn,m=mm;
		for (int i=1;i<=n;++i)
			for (int j=1;j<=m;++j)
				a[i][j]=x?i==j:0;
	}
	friend node operator *(node a,node b){
		node res;res.init(0,a.n,b.m);
		for (int i=1;i<=a.n;++i)
			for (int j=1;j<=b.m;++j)
				for (int k=1;k<=b.n;++k)
					res.a[i][j]=(res.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%mod;
		return res;
	}
	friend node operator ^(node x,int p){
		node res;res.init(1,x.n,x.m);
		for (;p;x=x*x,p>>=1)if (p&1)res=res*x;
		return res;
	}
}x,y,z;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
pii a[N],b[N];
void solve(){
	int n=read(),m=read(),k=0;
	for (int i=1;i<=m;++i){
		int x=read(),y=read();
		a[i]={min(x,y),max(x,y)};
	}
	sort(a+1,a+1+m);
	for (int i=1;i<=m;++i)
		if (a[i].fi>b[k].se)
			b[++k]={a[i].fi,a[i].se};
		else b[k].se=max(b[k].se,a[i].se);
	x.init(0,1,2);
	x.a[1][1]=1;
	x.a[1][2]=1;
	y.init(0,2,2);
	y.a[1][1]=0,y.a[1][2]=-1;
	y.a[2][1]=1,y.a[2][2]=3;
	z.init(0,2,2);
	z.a[1][1]=0,z.a[1][2]=-1;
	z.a[2][1]=0,z.a[2][2]=2;
	for (int i=1;i<=k;++i){
		if (i>1)assert(b[i].fi>b[i-1].se);
		x=x*(y^(b[i].fi-b[i-1].se-1));
		x=x*z;//cout<<k<<"!"<<endl;
	}
	x=x*(y^(n-b[k].se));
	cout<<(x.a[1][2]+mod)%mod<<endl;
}
signed main(){
	int T=read();
	while (T--)solve();
    return 0;
}