CF1872D.Plus Minus Permutation

You are given $3$ integers — $n$, $x$, $y$. Let's call the score of a permutation$^\dagger$ $p_1, \ldots, p_n$ the following value:

$$(p\_{1 \\cdot x} + p\_{2 \\cdot x} + \\ldots + p\_{\\lfloor \\frac{n}{x} \\rfloor \\cdot x}) - (p\_{1 \\cdot y} + p\_{2 \\cdot y} + \\ldots + p\_{\\lfloor \\frac{n}{y} \\rfloor \\cdot y})$$

In other words, the score of a permutation is the sum of $p_i$ for all indices $i$ divisible by $x$, minus the sum of $p_i$ for all indices $i$ divisible by $y$.

You need to find the maximum possible score among all permutations of length $n$.

For example, if $n = 7$, $x = 2$, $y = 3$, the maximum score is achieved by the permutation $[2,\color{red}{\underline{\color{black}{6}}},\color{blue}{\underline{\color{black}{1}}},\color{red}{\underline{\color{black}{7}}},5,\color{blue}{\underline{\color{red}{\underline{\color{black}{4}}}}},3]$ and is equal to $(6 + 7 + 4) - (1 + 4) = 17 - 5 = 12$.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (the number $2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$, but the array contains $4$).

给你 $3$ 个整数：$n$、$x$、$y$。我们定义一个排列$^\dagger$ $p_1, \ldots, p_n$ 的得分为如下值：

$$(p_{1 \cdot x} + p_{2 \cdot x} + \ldots + p_{\lfloor \frac{n}{x} \rfloor \cdot x}) - (p_{1 \cdot y} + p_{2 \cdot y} + \ldots + p_{\lfloor \frac{n}{y} \rfloor \cdot y})$$

换言之，一个排列的得分等于所有下标 $i$（满足 $i$ 被 $x$ 整除）对应的 $p_i$ 之和，减去所有下标 $i$（满足 $i$ 被 $y$ 整除）对应的 $p_i$ 之和。

你需要在所有长度为 $n$ 的排列中，找出可能的最大得分。

例如，当 $n = 7$、$x = 2$、$y = 3$ 时，最大得分由排列 $[2,\color{red}{\underline{\color{black}{6}}},\color{blue}{\underline{\color{black}{1}}},\color{red}{\underline{\color{black}{7}}},5,\color{blue}{\underline{\color{red}{\underline{\color{black}{4}}}}},3]$ 实现，其得分为 $(6 + 7 + 4) - (1 + 4) = 17 - 5 = 12$。

$^\dagger$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中包含了 $4$）。

The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Then follows the description of each test case.

The only line of each test case description contains $3$ integers $n$, $x$, $y$ ($1 \le n \le 10^9$, $1 \le x, y \le n$).

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的描述仅有一行，包含 $3$ 个整数 $n$、$x$、$y$（$1 \le n \le 10^9$，$1 \le x, y \le n$）。

For each test case, output a single integer — the maximum score among all permutations of length $n$.

对于每个测试用例，输出一个整数——所有长度为 $n$ 的排列中的最大得分。

The first test case is explained in the problem statement above.

In the second test case, one of the optimal permutations will be $[12,11,\color{blue}{\underline{\color{black}{2}}},4,8,\color{blue}{\underline{\color{red}{\underline{\color{black}{9}}}}},10,6,\color{blue}{\underline{\color{black}{1}}},5,3,\color{blue}{\underline{\color{red}{\underline{\color{black}{7}}}}}]$. The score of this permutation is $(9 + 7) - (2 + 9 + 1 + 7) = -3$. It can be shown that a score greater than $-3$ can not be achieved. Note that the answer to the problem can be negative.

In the third test case, the score of the permutation will be $(p_1 + p_2 + \ldots + p_9) - p_9$. One of the optimal permutations for this case is $[9, 8, 7, 6, 5, 4, 3, 2, 1]$, and its score is $44$. It can be shown that a score greater than $44$ can not be achieved.

In the fourth test case, $x = y$, so the score of any permutation will be $0$.

第一个测试用例已在题目描述中说明。

在第二个测试用例中，一个最优排列为 $[12,11,\color{blue}{\underline{\color{black}{2}}},4,8,\color{blue}{\underline{\color{red}{\underline{\color{black}{9}}}}},10,6,\color{blue}{\underline{\color{black}{1}}},5,3,\color{blue}{\underline{\color{red}{\underline{\color{black}{7}}}}}]$。该排列的得分为 $(9 + 7) - (2 + 9 + 1 + 7) = -3$。可以证明，无法获得大于 $-3$ 的得分。注意：本题的答案可以为负数。

在第三个测试用例中，排列的得分为 $(p_1 + p_2 + \ldots + p_9) - p_9$。该情况的一个最优排列是 $[9, 8, 7, 6, 5, 4, 3, 2, 1]$，其得分为 $44$。可以证明，无法获得大于 $44$ 的得分。

在第四个测试用例中，$x = y$，因此任意排列的得分均为 $0$。