A. Snakes 的 Naïve Graph

内存限制:512 MiB 时间限制: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 有一条无向边,当且仅当下列条件至少有一条成立:

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

样例

样例输入

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

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