作为一名老程序员，蒜斜深受颈椎病的困扰。今天，在医生的建议下，蒜斜决定去游泳馆游泳。

蒜斜发现，游泳池被一些泳道线划分成了若干个泳道。每一条泳道线都由一些不同颜色的浮标的组成：这些浮标形成了一些长度类似的颜色段，看上去十分美观。

然而，当蒜斜仔细清点了每一种颜色的浮标数量之后，蒜斜发现尽管这些颜色段看上去长度一样，但是它们实际上使用的浮标数量是略有差异的。

蒜斜对这种现象很感兴趣，于是他进行了更多的探索。他发现只要相邻两个颜色段使用的浮标数量的差别在 $K$ 以内，那么从视觉上来说，这两段颜色看上去的长度就是差不多的。

经过测量，蒜斜发现每一条泳道的浮标数量总数永远都是 $n$ 且颜色段数量永远都是 $m$。蒜斜想要计算在 (1) 浮标数量和颜色段数量保持不变，且(2) 任何相邻两段颜色段的长度从视觉上相同 的情况下，所有颜色段长度的方差最大值是多少。

简化题面：已知一个正整数数组 $A$ 的长度是 $m$ ，里面所有数字的和是 $n$ 且任何两个相邻数字差的绝对值不超过 $K$，你需要计算 $A$ 中所有数字的方差最大值是多少。

输入格式

输入第一行包含一个整数 $t(1\le t\le {10}^4)$，表示数据组数。

对于每组数据，输入一行三个整数 $n,m,K(1\le n\le {10}^8,1\le m\le 100,0\le K\le {10}^8)$，分别表示浮标的总数，颜色段的数量以及相邻两端浮标数量差的上限。

输出格式

对于每一组数据，输出一行一个整数，表示方差的最大值乘以 $m^2$（可以证明这个数值一定是一个整数）。如果不存在满足条件的方案，则需要输出 $-1$。

样例一

input

4
4 2 1
4 2 2
100000000 100 1
1919810 11 4514

output

0
4
8085000
24654303406

input

在第一组数据中，最优解是将两段的长度都设置为 $2$，这个时候方差为 $0$。

在第二组数据中，最优解是将两端的长度分别设置为 $1$ 和 $3$，这个时候方差为 $((2-1{)}^2+(2-3{)}^2)/2=1$。

限制与约定

Small Task: $K=1$。

Large Task: 无特殊限制。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载