e-olymp
Problems

Repair

Repair

Your favorite uncle is the director of the company that makes renovation in offices. In connection with the financial and economic crisis, the uncle decided to optimize his business.

It has long been rumored that the team leader in the uncle's firm buys the excess amount of building materials, and the remainder is used to furnish his new house. Your uncle is interested how many cans of paint he needs to paint the walls in the office of length L meters, width of W and height of H, if one can of paint enough for 16m2, and the size of doors and windows can be ignored? There is a lot of orders, so my uncle asked to write a program that will calculate everything.

Input

The first line contains the number of orders. Description of each order consists of three positive integers L, W, H – the length, width and height of the office in meters, respectively, each of which does not exceed 1000.

Output

For each order print in a separate line the number of cans of paint needed to paint the office.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
2
8 8 2
1 1 3
Output example #1
4
1