1003. 太近就不合法了

题目描述

有 $n$ 个依次排列的位置，编号为 $1,2,\ldots,n$。

每次询问给出两个整数 $x,k$。你需要选择若干位置，使位置 $x$ 不被选择，并且任意两个被选择位置的编号之差的绝对值不小于 $k$。

每次询问相互独立。求每次询问的合法选择方案数，允许不选择任何位置，答案对 $998244353$ 取模。

输入格式

第一行包含一个整数 $T$，表示测试用例的组数。

对于每组测试用例，第一行包含两个整数 $n,q$，分别表示位置数量和询问数量。

接下来 $q$ 行，每行包含两个整数 $x_i,k_i$，表示一次询问。

对于 OJ 中唯一一个正式测试点，保证：

$T=10^4$；

$1\le n,q\le 10^5$；

$1\le x_i,k_i\le n$；

$\sum n=10^6$；

$\sum q=10^6$。

输出格式

对于每次询问，输出一行一个整数，表示合法选择方案数对 $998244353$ 取模后的结果。

样例输入

3
5 2
3 2
4 3
1 2
1 1
1 1
3 2
2 1
1 3

样例输出

9
7
1
1
4
3

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1003