P8177 "EZEC-11" Arithmetic Progression.

You are given an arithmetic progression $x$ of length $n$, with first term $a$ and common difference $d$. Choose any two numbers $x_i, x_j$ from $x$ ($i\neq j$), and they must satisfy at the same time: - $x_i + x_j$ is even. - $\frac{x_i + x_j}{2}$ is not in $x$. Then you may add $\frac{x_i + x_j}{2}$ into $x$. This is called one operation. **Note: Newly added numbers can also be chosen.** What is the maximum number of operations you can perform?

**This problem has multiple sets of testdata.** The first line contains a positive integer $T$, the number of testdata sets. For each testdata set, one line contains three integers $n, a, d$.

For each testdata set, output one integer per line, the maximum number of operations.

**[Sample 1 Explanation]** For the first set of testdata, $x=[1,2,3]$, so no operation can be performed. For the second set of testdata, $x=[2,4]$. You can choose $2$ and $4$, and add $\frac{2+4}{2}=3$ into the sequence. **[Constraints and Notes]** **This problem uses bundled tests.** - 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): no special restrictions. For $100\%$ of the data, $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$. Translated by ChatGPT 5