Security Plan

传送门

容易发现，只要 \(4\) 个就一定可以覆盖所有格子。所以算法呼之欲出：

大力分讨！

那么一个的只可能是四个角 （靠不一定是四个。。）

Notice： \(n=1,m=1\) 之类的边界再分讨时尤为重要

两个的只可能是相同或相对的边界中。（其实画着画着就能发现一般来说最难覆盖的就是四个角，所以可以根据最多覆盖角的个数来给所有格子分类）

三个的就很多了：
①相邻边界两个，内部一个
②边界一个，内部两个。

这里说下我的心路历程：先固定边界的，然后移动内部：哦！同居一侧可以，分居两侧。。额若都紧挨着边界那一行也行。好开写！怎么样例 WA 了？？？手模后发现只要有一个紧挨着边界就可以了。改完一交，WA 飞了。苦思冥想，发现漏考虑边界了，再改！还是 WA。然后直到拿到标程我才查出错：内部格子数很大，要先取模再运算。

Notice：取模错误可能不是表达式漏写取模，而是变量本身就超过了。

四个的只可能是内部选四个，证明略

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
const long long jc2=499122177,jc3=332748118,jc4=291154603;
inline long long power(long long x,int c){
	long long now=1;
	while(c){
		if(c&1)now=now*x%mod;
		x=x*x%mod;c>>=1;
	}
	return now;
}
inline long long C1(long long n){//C(n,1)
	return max(0ll,n)%mod;
}
inline long long C2(long long n){//C(n,2)
	if(n<=0)return 0;
	return n*(n-1)%mod*jc2%mod;
}
inline long long sum1(long long n){//1-n ??? 
	if(n<0)return 0;
	return n*(n+1)%mod*jc2%mod;
}
inline long long sum2(long long n){//1-n ??????? 
	return (n*n%mod*n%mod+3*sum1(n)%mod-n+mod)%mod*jc3%mod;
}

int main(){
	int t;cin>>t;
	while(t--){
		long long n,m;cin>>n>>m;
		long long ans1=0,ans2=0,ans3=0,ans4=0,h=n-2,l=m-2,x=h*l; 
		if(n==1||m==1){
			if(n==m)ans1=1;
			else ans1=2;
		}
		else ans1=4;
		if(h>=0)ans2=(ans2+C2(2*l))%mod;
		else ans2=(ans2+C2(l))%mod;
		if(l>=0)ans2=(ans2+C2(2*h))%mod;
		else ans2=(ans2+C2(h))%mod;
		if(x>0){
			x%=mod;
			ans3=(ans3+C1(2*h)*C1(2*l)%mod*x%mod)%mod;
			ans3=(ans3+C1(2*h-4)*l%mod*l%mod+C1(2*l-4)*h%mod*h%mod)%mod;
			ans3=(ans3+2%mod*(sum2(h)*l%mod*l%mod-sum1(h)*l%mod)%mod-2*h%mod*C2(l)%mod)%mod;
			ans3=(ans3+2%mod*(sum2(l)*h%mod*h%mod-sum1(l)*h%mod)%mod-2*l%mod*C2(h)%mod)%mod;
			if(h>3)ans3=(ans3+4*l%mod*l%mod*sum1(h-3)%mod)%mod;
			if(l>3)ans3=(ans3+4*h%mod*h%mod*sum1(l-3)%mod)%mod;
			
			ans4=x*(x-1)%mod*(x-2)%mod*(x-3)%mod*jc4%mod;
		}
		cout<<((ans1+ans2+ans3+ans4)%mod+mod)%mod<<endl;
	}
	return 0;
}