eolymp
bolt
Try our new interface for solving problems
Problems

Repair

Repair

Time limit 1 second
Memory limit 128 MiB

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 16m^2, 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 data

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 data

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

Examples

Input example #1
2
8 8 2
1 1 3
Output example #1
4
1