Hitagi Senjougahara 有一张高度为 $h$、宽度为 $w$ 的纸张。这张纸被划分为 $1 \times 1$ 的网格。 假设纸张的左下角坐标为 $(0, 0)$，右上角坐标为 $(h, w)$。

Hitagi 可以进行多次裁剪，每次裁剪可以是水平的或垂直的。对于水平裁剪，Hitagi 选择一个整数高度 $h' \in [1, h - 1]$，并切开所有穿过该水平线的纸张。对于垂直裁剪，Hitagi 选择一个整数宽度 $w' \in [1, w - 1]$，并切开所有穿过该垂直线的纸张。因此，如果她在不同的高度进行 $c_h$ 次水平裁剪，在不同的宽度进行 $c_w$ 次垂直裁剪，她最终将得到 $(c_h + 1)(c_w + 1)$ 张纸片。

现在 Hitagi 想知道，为了使最终得到的所有矩形纸片的面积都不超过 $s$，最少需要进行多少次裁剪。

你的任务是求出 $t$ 组三元组 $h, w, s$ 的答案。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 1\,000$) —— 需要解决的测试用例数量。

接下来的 $t$ 行，每行包含三个整数 $h, w, s$ ($1 \le h, w, s \le 10^9$) —— 纸张的尺寸和期望的最大面积。

输出格式

输出 $t$ 行，每行包含一个整数 —— 对应三元组的答案。

样例

输入样例 1

5
2 2 1
1 7 2
4 4 17
4 4 15
120 216 34

输出样例 1

2
3
0
1
55