A19335.大数求和

时间限制：2000ms
内存限制：512MB

求 $\sum_{k=1}^{N} k$ 对 $M$ 取余的结果。

$\bf{每个测试文件包含 T 个测试用例。}$

$\large{数据范围}$

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 10^{4 \times 10^6}$
• $1 \le M \le 10^9$
• 题目保证对于所有的测试用例 $N$ 的总数不超过 $10^{4 \times 10^6}$。

每个测试文件格式如下：

$T$
$Testcase_1$
$Testcase_2$
$\vdots$
$Testcase_T$

对于每个 $Testcase$ 格式如下：

$N$ $M$

对于每个 $Testcase$ 在单独的一行中输出答案。

• 第一个测试用例：$\sum_{k=1}^{3}k = 1+2+3=6$ 对 $100$ 取余的结果为 $6$。
• 第二个测试用例：$\sum_{k=1}^{5}k = 1+2+3+4+5=15$ 对 $10$ 取余的结果为 $5$。