给定一个长度为 $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$。
对于每组数据，输出一行一个非负整数，表示平均数为整数的子段个数。
【样例解释】
在第一组数据中，$a = [1, 3]$。共有 $3$ 个连续非空子串满足要求：
在第二组数据中，$a = [2, 7, 12]$。共有 $4$ 个连续非空子串满足要求：
【数据范围】
| 测试点编号 | $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$）。
3 2 1 2 3 2 5 11451 41 91981
3 4 32787076