#[563].「LibreOJ Round #10」Snakes 的 Naïve Graph

内存限制：512 MB 时间限制：1000 ms

对于一个数 $m$，我们按如下方式确定一个有 $(2m-2)$ 个点的无重边二分图 $G(m)$：

二分图 $G(m)$ 是一个可黑白二染色的无向图，其中有 $(m-1)$ 个黑色点与 $(m-1)$ 个白色点。令所有黑色点构成的集合为 $X$ ，所有白色点构成的集合为 $Y$。

令 $i_X$ 表示集合 $X$ 的编号为 $i$ 的点，$i_Y$ 表示集合 $Y$ 的编号为 $i$ 的点，其中满足 $1\leq i\leq m-1$ 。$i_X$ 与 $j_Y$ 有一条无向边，当且仅当下列条件至少有一条成立：

令 $f[G(m)]$ 表示 $G(m)$ 的本质不同的最大匹配的个数。两个匹配本质不同当且仅当存在 $i_X$ 使得其在一种方案中与 $j_Y$ 匹配，在另一种方案中不与 $j_Y$ 匹配。

共 $q$ 组询问，每组询问给出 $l,r$ ，求 $\sum_{i=l}^r f[G(i)]$。

输出答案对 $311021$ 取模的结果。

第一行包含一个正整数 $q$，表示数据组数。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一组询问。

共 $q$ 行，每行一个整数，表示 $\sum_{i=l}^r f[G(i)]$ 对 $311021$ 取模的结果。

对于全部数据，满足 $1\leq l\leq r\leq 10^7$，$1\leq q\leq 10^5$。

子任务编号	分值	$l,r\leq$	$q\leq$
1	$10$	$100$	$10$
2	$9$	$1000$	$10^5$
3	$12$	$5000$	$10^5$
4	$13$	$2\times 10^4$	$10^5$
5	$15$	$5\times 10^5$	$10^5$
6	$18$	$2\times 10^6$	$10^5$
7	$23$	$10^7$	$10^5$

563 「LibreOJ Round #10」Snakes 的 Naïve Graph