题目描述

小Z 在 $[L,R]$ 的范围中至少挑选 $k$ 个互不重复的数字构成一个集合 $S$。

然后他计算了 $S$ 中数字的总和、最大值、最大公约数，分别为 $S,M,G$

求出 $(S-M)\times G$ 可能的最大值

输入格式

第一行输入一个整数 $t$ 代表数据组数，每组测试数据描述如下：

一行三个正整数 $l,r,k$，分别表示待选取的区间，以及至少需要选择的数字个数。

输出格式

对于每组测试数据：

在单独的一行输出一个整数，表示题中所求式子的最大值。

输入输出样例

2
1 2 1
2 3 2

1
2

样例 $\tt \#1$说明

对于第一组测试数据，最优策略是加入 $1,2$。

对于第二组测试数据，唯一的合法策略只有加入 $2,3$。

数据范围

$100\%:1 \leq l \leq r \leq 10^{9}, 1 \leq k \leq r-l+1,1\le t\le 10^5$