题目内容

运维侧做容量水位分析时，两条整型指标序列在偏移 $i$ 处的读数分别为 $x+i$ 与 $y+i$。定义对齐公约

其中 $\gcd$ 表示最大公因数。例如 $8$ 与 $12$ 的正公约数有 $1,2,4$，故 $\gcd(8,12)=4$。现要对连续偏移窗口做汇总：求

即 $\displaystyle\sum_{i=s}^{t}\gcd(x+i,\,y+i)$。结果可能很大，对 $1000000007$ 取模后写出。

输入描述

第一行一个整型 $k$（$1 \le k \le 120$），表示随后有 $k$ 行询问。

接下来 $k$ 行，每行四个整型 $x,y,s,t$（$1 \le x,y \le 100000$，$0 \le s \le t \le 1\times 10^{18}$）。

请对每个询问逐一计算上述和模 $1000000007$。

输出描述

共写出 $k$ 行。对每一个询问，写出一个非负整型，即该窗口公约和模 $1000000007$ 的结果。

样例1

输入

3
8 14 0 2
5 5 1 3
3 9 0 4

输出

7
21
13

说明

三个询问依次为：$\gcd(8,14)+\gcd(9,15)+\gcd(10,16)=2+3+2=7$；两路读数相同，和为 $6+7+8=21$；$\gcd(3,9)+\gcd(4,10)+\gcd(5,11)+\gcd(6,12)+\gcd(7,13)=3+2+1+6+1=13$。

样例2

输入

2
2 10 0 0
7 11 2 5

输出

2
8

说明

第一问窗口只有 $i=0$，$\gcd(2,10)=2$。第二问 $i=2$ 到 $5$：$\gcd(9,13)+\gcd(10,14)+\gcd(11,15)+\gcd(12,16)=1+2+1+4=8$。