Youth Hostel Dorm

Time limit1sMemory limit128 MB

Summary

Find the maximum number of beds that can be placed in an l by w grid so every bed stays reachable from a single boundary entrance via floor tiles.

Level: Medium6 of 10
Topics: Combinatorics, Greedy, Brute force
Solved: No attempts yet

Problem

A youth hostel has a single large dorm shaped as an $l \times w$ grid of unit squares. You must design the room's layout by writing exactly one of three symbols in every square:

E — the entrance. There is exactly one entrance, and it must lie on the boundary of the grid.
. — empty floor that can be walked on.
B — a bed.

You may move between two squares only when they share a horizontal or vertical edge, and you may only ever stand on the entrance or on empty floor, never on a bed. A bed is usable when, starting at the entrance and walking only across entrance and empty squares, you can reach some square that is horizontally or vertically adjacent to that bed. A layout is valid only if every one of its beds is usable.

Among all valid layouts of the room, determine the largest possible number of beds.

Input

The first line contains an integer $T$ ( $1 \le T \le 100$ ): the number of dorms.

Each of the next $T$ lines contains two integers $l$ and $w$ ( $1 \le l, w \le 8$ ): the number of rows and the number of columns of one dorm.

Output

For each dorm, print a single line with one integer: the maximum number of beds that any valid layout of an $l \times w$ room can contain.

Examples4

Example 1
Input
```
3
1 1
4 7
3 8
```
Expected output
```
0
16
16
```
Example 2
Input
```
1
1 1
```
Expected output
```
0
```
Example 3
Input
```
2
1 8
8 1
```
Expected output
```
2
2
```

Example 4

Input

Expected output