【MX-X5-T1】「GFOI Round 1」Inverted World

> [Inverted World - ARForest](https://music.163.com/#/song?id=2099631232)

给定一个长度为 $n$ 的正整数序列 $(a_1, \ldots, a_n)$，**保证该序列是等差数列**。 （如果你不知道等差数列的定义，请参阅题目末尾处的提示。） 请求出该序列中满足如下条件的连续非空子串 $(a_l, \ldots, a_r)$（$1 \le l \le r \le n$）的数量： - 该子串中的元素的平均值是整数。 （即 $(a_l + \cdots + a_r) \div (r - l + 1)$ 是整数。） 该序列可能很长，即 $n$ 可能很大，故不会给出该序列的每一项，而是只给出长度 $n$、首项 $k$ 和公差 $d$。**保证 $\bm{k, d}$ 都是正整数**。

**本题有多组测试数据。** 第一行输入一个正整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行包含三个正整数 $n, k, d$。

对于每组数据，输出一行一个非负整数，表示平均数为整数的子段个数。

3
2 1 2
3 2 5
11451 41 91981

3
4
32787076

**【样例解释】** 在第一组数据中，$a = [1, 3]$。共有 $3$ 个连续非空子串满足要求： - $[1]$，其平均值为 $1$； - $[3]$，其平均值为 $3$； - $[1, 3]$，其平均值为 $2$。 在第二组数据中，$a = [2, 7, 12]$。共有 $4$ 个连续非空子串满足要求： - $[2]$，其平均值为 $2$； - $[7]$，其平均值为 $7$； - $[12]$，其平均值为 $12$； - $[2, 7, 12]$，其平均值为 $7$。 **【数据范围】** | 测试点编号 | $n \le$ | $k \le$ | $d \le$ | 分值 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $10$ | $10$ | $10$ | $28$ | | $2$ | $10^9$ | $10^9$ | $1$ | $35$ | | $3$ | $10^9$ | $10^9$ | $10^9$ | $37$ | 对于所有数据，满足 $1 \le T \le 10^3$，$1 \le n, k, d \le 10^9$。 **【提示】** 长度为 $n$、首项为 $k$、公差为 $d$ 的等差数列定义为 $a_1 = k$ 且 $a_i = a_{i - 1} + d$（对每个 $2 \le i \le n$）。