本题看似很难，实际上只需要找找规律就好。
先从样例入手。
样例给的例子是只有两行的特殊情况，我们可以先从这个特殊情况入手。
我们发现，当一条线向下穿过的时候，设与中间的线交点为 P。那么如果 P 不在格点上时，下一行就会从这列开始，如果 P 在格点上，那么就会从下一列开始。显然，前一种会比后一种多一个格子，所以只有前种策略最优。
再把问题的范围扩大到一般情况，有了上面的结论，我们可以发现，如果总格子是 \(n\times m\)。那么最优解一定是 \(n+m-1\)，证明如下。
首先这条线可以水平切，那么就是 \(n\) 个格子，然后我们再固定一端，把另一端向下移动。当这条线穿过了两行时，如果与中间的线的交点不在格点上，那么就会多出一个格子。再继续向下移动，直到穿过了 \(m\) 行，这时一共交了 \(m-1\) 条水平线，最多多产生 \(m-1\) 个格子被穿过。
综上所述，当总格子是 \(n\times m\) 时，最多可穿过 \(n+m-1\) 个格子。
于是，第一个问题就很容易地解决了。
再看看第二个问题，如果想要穿过的格子数大于等于 \(Q\)，也就代表 \(n'+m'-1\) 最小也要等于 \(Q\)。也就是说我们知道了 \(n'+m'\) 想要求满足 \(n'\leq n,m'\leq m\) 的情况下，使得 \(n'\times m'\) 最小。
小学数学老师告诉我们，矩形周长一定时，长宽差距越小，面积越大。所以，\(n'\) 或者 \(m'\) 某一个尽可能的小就可以让 \(n'\times m'\) 尽可能的大。显然，如果 \(n>m\) ，就让 \(m'=m,n'=Q+1-m\)，反之同理。
因为无论是 \(n'=n\) 还是 \(m'=m\)，对应的 \(m'-m\) 和 \(n'-n\) 的值都是 \(Q+1-n-m\)。所以第二问的答案就是 \(\min(n,m)\times(Q+1-n-m)\)。
AC 代码
#include<bits/stdc++.h>
using namespace std;
const unsigned long long mod=998244353;//因为数据比较大，所以我直接开的unsigned long long
unsigned long long n,m,k,d;
int T;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%llu%llu%llu",&k,&n,&m);
if(k==1) printf("%llu\n",n+m-1);
else scanf("%llu",&d),d=d+1-n-m,d%=mod,printf("%llu\n",min(n,m)%mod*d%mod);
}
return 0;
}