解题思路
本题考查数论恒等式 + 欧拉函数。直接枚举 i 不可行，因为 t−s 可达 1018。
- 利用 gcd(u,v)=gcd(u,v−u)，得到
gcd(x+i,y+i)=gcd(x+i,∣y−x∣)。记 D=∣y−x∣。
- 若 D=0，则每一项都是 x+i，窗口和为等差数列
(t−s+1)⋅x+2(s+t)(t−s+1)，再取模。
- 若 D>0，令 L=x+s、R=x+t，问题变成求 ∑n=LRgcd(n,D)。
题目内容
运维侧做容量水位分析时，两条整型指标序列在偏移 i 处的读数分别为 x+i 与 y+i。定义对齐公约
h(i)=gcd(x+i,y+i)
其中 gcd 表示最大公因数。例如 8 与 12 的正公约数有 1,2,4，故 gcd(8,12)=4。现要对连续偏移窗口做汇总：求
h(s)+h(s+1)+⋯+h(t)
即 i=s∑tgcd(x+i,y+i)。结果可能很大，对 1000000007 取模后写出。
输入描述
第一行一个整型 k（1≤k≤120），表示随后有 k 行询问。
接下来 k 行，每行四个整型 x,y,s,t（1≤x,y≤100000，0≤s≤t≤1×1018）。
请对每个询问逐一计算上述和模 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。
