Try our new interface for solving problems



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.


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.


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 128 MiB
Input example #1
8 8 2
1 1 3
Output example #1