题目介绍

本题为最大差排列数据加强版，唯一不同的地方是本题中$1 \leq t \leq 10,000$。

这是一道简单的数学题。 给你 $3$ 个整数 $n$，$x$，$y$。我们把一个排列 $p_{1},...,p_{n}$ 的得分规定为：

$(p_{1⋅x}+p_{2⋅x}+…+p_{⌊\frac{n}{x}⌋⋅x})−(p_{1⋅y}+p_{2⋅y}+…+p_{⌊\frac{n}{y}⌋⋅y})$ 例如，一个排列为 $[2,6,1,7,5,4,3]$且 $x$ 为 2， $y$ 为 3。

那么它的得分为 $(6+7+4)−(1+4)=17−5=12$。

换言之，得分为排列 $p$ 中下标为 $x$ 的倍数的点的总和，减去下标为 $y$ 的倍数的点的总和。

求一个排列使得它的得分最大，输出最大得分。长度为 $n$ 的排列是由从 $1$ 到 $n$ 的任意顺序的 $n$ 个不同整数组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是一个排列（$n=3$，但数组中包含 $4$）。

输入

第一行输入包含一个整数 $t (1 \le t \le 10^{4})$ --测试用例数。

然后是每个测试用例的描述。

每个测试用例描述的唯一一行包含 $3$ 个整数 $n$、$x$、$y$ $(1\le n \le 10^{9}, 1 \le x, y \le n)$。

输出

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

样例

8
7 2 3
12 6 3
9 1 9
2 2 2
100 20 50
24 4 6
1000000000 5575 25450
4 4 1

12
-3
44
0
393
87
179179179436104
-6