题目描述

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