题目描述

小 Z 家有 $1$ 个大小为 $n\times m$ 的空地，他和朋友们玩游戏：可以用绳子随意在花园中圈出一块方形（即长和宽分别在 $1\sim n$ 和 $1\sim m$ 之间），谁最后用的绳子的总长度更接近 $k$ 的为胜者。

询问小 Z 要赢的话，他用的绳子与 $k$ 最小的差距是多少。

本题目有多组询问。

输入格式

第一行，$1$ 个正整数 $q$，表示数据组数。

接下来 $q$ 行，每行 $3$ 个正整数 $n,m,k$。

输出格式

$q$ 行，表示每组数据的结果，即围成的方形周长与 $k$ 的最小差距。

输入输出样例

4
5 5 12
3 4 5
2 1 9
34 45 1

0
1
3
3

样例 $\tt \#1$说明

• 第一组数据中，选择 $2\times4$ 方形的周长为 $12$，与 $k$ 差距最小为 $0$
• 第二组数据中，选择 $2\times1$ 方形的周长为 $6$，与 $k$ 差距最小为 $1$
• 第三组数据中，选择 $2\times1$ 方形的周长为 $6$，与 $k$ 差距最小为 $3$

数据范围

• 对于 $60\%$ 的数据，$1\le q,n,m,k\le 100$
• 对于 $100\%$ 的数据，$1\le n,m,k\le 10^8,1\le q\le 10^5$