题目描述

你正在参加国际构造排列大赛(International Construct Permutation Contest, ICPC)，设 $\left[ a_i \right]$ 是公差为 $d$ 的等差数列，一共有 $n$ 项。给定首项 $a_1$，请你将 $\left[ a_i \right]$ 重新排列为 $\left[ p_i \right]$ 并尝试求出

的最小值。

输入描述

本题包含多个测试数据，第一行输入一个整数 $t$ 表示数据组数，其中 $1\leqslant t\leqslant 1\times 10^4$

接下来 $t$ 行，每行输入一行由 $3$ 个由空格隔开的整数 $n,d,a_1$，满足 $2\leqslant n\leqslant 1\times 10^5,0\leqslant d\leqslant 1\times10^9,1\leqslant a_i\leqslant 1\times10^9$。

保证所有测试点的 $\sum n\leqslant 2\times 10^5$。

输出描述

对于每个测试用例输出一个数，表示 $S$ 的最小值，请使用换行分隔输出每一组用例的结果。

样例

3
5 1 4
4 6 4
7 0 4

4
6
24