D. Плюс минус перестановка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$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})$$$$$$

Другими словами, счёт перестановки — это сумма $$$p_i$$$ по всем индексам $$$i$$$, делящимся на число $$$x$$$, минус сумма $$$p_i$$$ по всем индексам $$$i$$$, делящимся на число $$$y$$$.

Вам нужно найти максимально возможный счёт среди всех перестановок длины $$$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$$$.

Пример
Входные данные
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
Примечание

Первый набор входных данных разобран в условии задачи выше.

Во втором наборе входных данных одной из оптимальных перестановок будет $$$[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$$$.