「EZEC-11」等差数列

给你一个长为 $n$，首项为 $a$，公差为 $d$ 的等差数列 $x$。 从 $x$ 中任选两个数 $x_i,x_j$（$i\neq j$），同时满足： - $x_i+x_j$ 为偶数。 - $x$ 中没有 $\frac{x_i+x_j}{2}$。 那么你就可以将 $\frac{x_i+x_j}{2}$ 加入 $x$ 中，称为一次操作。 **注意：新加入的数也可被选择。** 问你最多能进行几次操作？

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

对于每组测试数据，一行一个整数表示最多的操作次数。

2
3 1 1
2 2 2

0
1

**【样例 1 解释】** 对于第一组数据，$x=[1,2,3]$，无法进行任何操作。 对于第二组数据，$x=[2,4]$，可以选择 $2$ 和 $4$，将 $\frac{2+4}{2}=3$ 加入数列中。 **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1（10 points）：$d=1$。 - Subtask 2（10 points）：$n=2$。 - Subtask 3（30 points）：$T\le 10$，$n\times d\le 10^3$，$a=0$。 - Subtask 4（50 points）：无特殊限制。 对于 $100\%$ 的数据，$1\le T\le 10^5$，$2\le n\le 10^9$，$-10^9\le a\le 10^9$，$1\le d\le 10^9$。