← Home
write a go solution for Description:
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,colorredunderlinecolorblack6,colorblueunderlinecolorblack1,colorredunderlinecolorblack7,5,colorblueunderlinecolorredunderlinecolorblack4,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).

Input Format:
The first line of input contains an integer t (1<=t<=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<=n<=10^9, 1<=x,y<=n).

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

Note:
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,colorblueunderlinecolorblack2,4,8,colorblueunderlinecolorredunderlinecolorblack9,10,6,colorblueunderlinecolorblack1,5,3,colorblueunderlinecolorredunderlinecolorblack7]. 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.. Output only the code with no comments, explanation, or additional text.