对于一个数 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 取模的结果。
5 270 352 24 28 319 637 312 932 502 743
1926 817 404 65535 114514
对于全部数据，满足 1\leq l\leq r\leq 10^7 ， 1\leq q\leq 10^5 。
