Description

本题为简单的数学题数据减弱版，唯一不同的地方是本题中$1 \leq T \leq 1,000$。

给你三个数，n,x,y，对一个排列P，给定一个函数f(x)=$\sum_{i=1}^{\lfloor n/x \rfloor}p_{i*x}$。 对于所有的长度为n的排列，计算出f(x)-f(y)的最大值。

Format

Input

多组测试数据。 第一行输入一个整数T($1 \le T\le1000$) 接下来描述每一组测试数据。 只有一行输入包含3个整数n,x,y($1 \le n\le10^{9}，1 \le x,y\le n$)。

Output

对每一组测试数据，输出答案。

Samples

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

Limitation

1s, 256M for each test case.