Nikodim 家的院子里最近布置了一个花坛。邻居家的狗经常跑过花坛，Nikodim 决定保护这些花。他计划在花坛周围围上一圈小栅栏。

在“园艺全能”商店里，你可以买到长度为 $s$ 的塑料栅栏段。购买后，如果顾客需要，售货员可以将一些初始的栅栏段切割成恰好两段任意长度（不一定是整数长度）的小栅栏段。切割后的新栅栏段不能再被切割。不同的初始栅栏段可以被切割成不同长度的新栅栏段。

花坛是一个 $w \times h$ 的矩形。Nikodim 想要制作一个恰好符合这个尺寸的栅栏。为此，矩形的每一条边都应该表示为若干栅栏段的和（每段栅栏最多只能使用一次）。注意，不需要使用栅栏段的所有部分。

请确定他最少需要购买多少段长度为 $s$ 的栅栏。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。

接下来的 $t$ 行，每行包含三个整数 $w, h, s$ ($1 \le w, h, s \le 10^8$)，分别表示花坛的尺寸和栅栏段的长度。

输出格式

对于每个测试用例，输出 Nikodim 为了围成栅栏最少需要购买的长度为 $s$ 的栅栏段数量。

样例

样例输入 1

7
7 9 4
1 1 2
1 1 4
4 6 2
3 3 5
10 6 4
1 11 5

样例输出 1

8
2
4
10
4
8
5

说明

在第一个测试用例中，需要购买 8 段栅栏。之后，可以将两段栅栏切割成长度为 1 和 3 的小段。这样就可以围成栅栏：两次 $7 = 4 + 3$ 以及两次 $9 = 4 + 4 + 1$。