题目背景

Inverted World - ARForest

题目描述

给定一个长度为 $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$。

数据范围

对于所有数据，满足 $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$）。