Youth Hostel Dorm

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.

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.

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.