给你 $$$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$$$ 整除的所有索引 $$$p_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$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$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$$$ 的排列中的最高分数。
示例
输入 #1
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
输出 #1
12 -3 44 0 393 87 179179179436104 -6
注意
第一个测试用例在上面的问题陈述中进行了解释。
在第二个测试用例中,最佳排列之一将是$$$[12,11,\颜色{蓝色}{\下划线{\颜色{黑色}{2}}},4,8,\颜色{蓝色}{\下划线{\颜色{红色}{\下划线{\颜色{黑色}{9}}}}} ,10,6,\颜色{蓝色}{\下划线{\颜色{黑色}{1}}},5,3,\颜色{蓝色}{\下划线{\颜色{红色}{\下划线{\颜色{黑色}{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$$$。