Problem Statement

Alice lives in a town on an infinitely extending two-dimensional plane. Her home is at the origin, that is, at coordinates $(x, y) = (0, 0)$.

In this town, there are roads represented by the line $x = An$ for every non-negative integer $n$ and the line $y = Bm$ for every non-negative integer $m$. There are no other roads.

Alice wants to choose $1$ point $(x, y)$ in this town and build a cafe there. A candidate location $(x, y)$ for the cafe must satisfy all of the following conditions.

• $x$ and $y$ are both positive integers.
• The Manhattan distance from her home $(0, 0)$ is at most $N$. That is, $x + y \leq N$ holds.
• $(x, y)$ can be reached from her home $(0, 0)$ by traveling only along roads.

How many points are possible as a candidate location $(x, y)$ for the cafe?

You are given $T$ test cases; solve each of them.

Input

The input is given from standard input. The $1$st line is given in the following format.

$T$

Then, $T$ test cases follow, each given in the following format.

$N$ $A$ $B$

Output

Print $T$ lines. On the $i$-th $(1 \leq i \leq T)$ line, print the answer to the $i$-th test case.

It can be proved that under the constraints of this problem, the answer is less than $2^{63}$.

Print a newline at the end.

Sample

Sample 1

Input

5
10 2 3
8 9 10
1200 1 2
31415 92 65
123456789 12345 67890

Output

27
0
719400
12841651
729437374182

$5$ test cases are given.

In the $1$st test case, as shown in the figure below, there are roads represented by the lines $x = 0, x = 2, x = 4, x = 6, \dots$ and $y = 0, y = 3, y = 6, y = 9, \dots$.

For example, $(2, 2)$, $(6, 3)$, and $(1, 9)$ have a Manhattan distance of at most $10$ from her home and can be reached by traveling along roads via routes such as those shown in the figure above, so they satisfy the conditions for building a cafe. There are other coordinates that satisfy the conditions as well, and there are $27$ candidate locations in total.

In the $2$nd test case, there are no coordinates where a cafe can be built. Print $0$. Note that for the coordinates where the cafe is built, both $x, y$ must be positive.

Note that the answer may not fit in a 32bit integer.