Mountain Shelter

While Hektor was busy working on the HektorJudge project, his colleague Wiktor decided that life should not consist only of sitting in front of a computer, so he set off on a trip to the mountains. When he reached the mountain shelter in the evening, he was surprised to find that he was not the only one who had thought of spending the weekend in the mountains: the shelter was packed with tourists!

In this awkward situation, the shelter's manager had to arrange for the tourists to sleep on the floor of the shelter's main hall. The hall is a rectangle made up of $W \times K$ square cells arranged in $W$ rows and $K$ columns. Each tourist occupies exactly two adjacent cells (touching either horizontally or vertically). What is the maximum number of tourists that can be placed in a hall of the given size so that each cell is used by at most one tourist? Wiktor, being skilled in mathematics and computer science, immediately worked out the correct answer.

The first line contains a natural number $Z$ ($1 \le Z \le 10$), the number of test sets. The test sets follow, one after another.

Each test set consists of a single line containing two positive integers $W$ and $K$ ($1 \le W, K \le 1000$), separated by a single space.

For each test set, print on its own line the maximum number of tourists who can sleep in the shelter hall at the same time. The order of the printed answers must match the order of the test sets in the input.