琪露诺的连续取模求和

题号：NC307910
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 在幻想乡的雾之湖旁，冰之妖精琪露诺正在享受一个悠闲的下午。作为"最强"的妖精，她总是喜欢挑战各种难题。今天，她发现了一种有趣的数字游戏——连续取模运算！

$\hspace{15pt}$ 琪露诺想象自己正在用冰晶冻结数字：每个数字 $i$ 代表一颗冰晶，她需要依次用从 $q$ 到 $p$ 的"冰封模数"来冻结它。每次取模操作就像施加一层冰霜，数字逐渐缩小，最终留下一个余数。
$\hspace{15pt}$ 琪露诺想知道，如果她处理从 $l$ 到 $r$ 的所有冰晶，最终剩下的冰晶能量总和是多少？形式化地说，对于给定两个整数区间 $[l,r]$ 和 $[p,q]$ ，你需要计算以下式子的结果：

$\displaystyle \sum\limits_{i=l}^r \big( i \bmod (q) \bmod (q-1) \bmod (q-2) \bmod \cdots \bmod (p) \big)$

$\hspace{15pt}$ 简单来说，计算结果为：对区间 $[l,r]$ 内每一个整数 $i$ ，依次对从 $q$ 到 $p$ 内所有整数取模后求和。

【名词解释】
$\hspace{15pt}$ $\bmod$ ：代表取模运算。例如， $5$ 除以 $3$ 的余数为 $2$ ，因此记作 $5 \bmod 3 = 2$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

在一行上输入四个整数 ，表示整数区间和模数范围。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示式子的计算结果。

示例1

输入

复制

4
6 9 7 8
6 6 6 7
2025 2029 10 15
114 514 191 9810

输出

复制

说明

对于第一组测试数据：
对于整数 ，有 ；
对于整数 ，有 ；
对于整数 ，有 ；
对于整数 ，有 。
综上，计算结果为 。

对于第二组测试数据，有 ，答案为 。