A. Snakes 的 Naïve Graph

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

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

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

iXi_X 表示集合 XX 的编号为 ii 的点,iYi_Y 表示集合 YY 的编号为 ii 的点,其中满足 1im11\leq i\leq m-1iXi_XjYj_Y 有一条无向边,当且仅当下列条件至少有一条成立:

  • i=ji=j
  • i×j1(modm)i\times j\equiv 1\pmod m

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

qq 组询问,每组询问给出 l,rl,r ,求 i=lrf[G(i)]\sum_{i=l}^r f[G(i)]

输出答案对 311021311021 取模的结果。

输入格式

第一行包含一个正整数 qq,表示数据组数。

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

输出格式

qq 行,每行一个整数,表示 i=lrf[G(i)]\sum_{i=l}^r f[G(i)]311021311021 取模的结果。

样例

样例输入

5
270 352
24 28
319 637
312 932
502 743

样例输出

1926
817
404
65535
114514

数据范围与提示

对于全部数据,满足 1lr1071\leq l\leq r\leq 10^71q1051\leq q\leq 10^5

子任务编号 分值 l,rl,r\leq qq\leq
1 1010 100100 1010
2 99 10001000 10510^5
3 1212 50005000 10510^5
4 1313 2×1042\times 10^4 10510^5
5 1515 5×1055\times 10^5 10510^5
6 1818 2×1062\times 10^6 10510^5
7 2323 10710^7 10510^5