Cube

WoodArt is a company famous for making sculptures out of wood. Mr. Kube, a sculptor at the company, wants to build artwork using only cubic wooden blocks of various sizes.

The raw lumber supplied to WoodArt is a rectangular block whose width, length, and height are $W$, $L$, and $H$. Mr. Kube cuts this lumber until every piece is a cube. A single cut takes one piece of wood and splits it into two rectangular blocks; he then repeats this on each resulting block until every piece is a cube. Mr. Kube wants to end with every piece a cube while making as few cuts as possible.

The lumber dimensions $W$, $L$, and $H$ are integers with $1 \le W, L, H \le 200$, and every resulting cube must have an integer side length of at least $1$.

Any material lost while cutting is ignored. That is, if a piece of size $W \times L \times H$ is cut into two pieces of size $W \times L \times H_1$ and $W \times L \times H_2$, then $H = H_1 + H_2$. The same holds for the $W$ and $L$ directions.

Input is given through standard input. The first line contains the number of test cases $T$ ($1 \le T \le 20$). Each of the following test cases is a single line with three integers $W$, $L$, $H$ ($1 \le W, L, H \le 200$) describing the size of the lumber.

For each test case, print on its own line the number of cube pieces produced when the lumber is cut using the minimum number of cuts.