题目描述

对于一个数 $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$ 有一条无向边，当且仅当下列条件至少有一条成立：

• $i=j$
• $i\times j\equiv 1\pmod m$

令 $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$ 取模的结果。

样例

input

5
270 352
24 28
319 637
312 932
502 743

output

1926
817
404
65535
114514

数据范围与提示

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