题目描述

给出正整数 $a,b,k$，找到两个整数 $x,y \in [0,k]$，最小化 $\text{LCM}(a+x,b+y)$ 并输出这个值。

输入格式

第一行一个正整数 $T$。

之后对于每组数据，给出三个正整数 $a,b,k$。

输出格式

对于每组数据，输出一行，输出一个整数，表示答案。

输入样例

3
3 8 4
2 101 100
99999999999998 100000000000000 1

输出样例

8
101
4999999999999900000000000000

说明提示

输入样例 #2

3
16220040981138 5666634080326 4
96649439266105 99078423788799 4
82236880034603 33417039399944 4

输出样例 #2

2703324617884289456082810
87910932115610821494459
25445491298566286237368524

输入样例 #3

3
63737803441132 6318706425971 120
50472959101381 57259631488372 120
75340843599831 24485154795581 120

输出样例 #3

24002650228540251764496
52409383401210065333760
414267284521635440114848

数据范围

对于 $100\%$ 的数据，$1 \leq T \leq 3$