Description

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?

Input Format

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$.

Output Format

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

2
3 1 1
2 2 2

0
1

Hint

[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