3916：植树问题

在一片网格形状（平面直角坐标系）的土地上种树，可以把数种在格子里，一个格子最多种一棵树，每棵树都有自己的坐标(x,y)。

定义：如果两棵树的坐标分别是(x1,y1)和(x2,y2)，那么这两棵树之间的距离s=max(|x1-x2|, |y1-y2|)，其中|...|是数学上的绝对值符号，max是数学上取两个数的最大值运算。

例如图中A、B两棵树的距离是2。

树木之间需要保持一定的距离，否则容易种不活。

现在已知这是一个a行b列的网格，任意两棵树之间的距离不能小于c，问这片土地上最少需要种几棵树就可以确保无法再多种下一棵树。

这是一道多组案例的题目，一个正整数n，表示案例的数量。（n<=1000）

每组案例由3个正整数a、b、c组成，表示土地由a行b列的网格组成，树与树之间的间隔至少要为c。（a<=10000, b<=10000, c<=100）

针对每组案例，输出一个整数，表示土地上至少需要种下多少棵树才能保证无法再多种一棵树。

每组案例输出后都要换行。

2

4 5 2

1 5 3

4

1

22-23(1)第4次线上赛