유스호스텔 도미토리

어느 유스호스텔에는 $l \times w$ 크기의 단위 정사각형 격자 모양인 커다란 도미토리(공동 침실)가 하나 있습니다. 당신은 이 방의 배치도를 만들어야 하며, 모든 칸에 다음 세 가지 기호 중 정확히 하나를 적습니다.

• E — 출입구. 출입구는 정확히 하나이며, 반드시 격자의 가장자리(경계)에 있어야 합니다.
• . — 지나다닐 수 있는 빈 바닥.
• B — 침대.

두 칸이 상하좌우로 변을 맞대고 있을 때에만 서로 이동할 수 있으며, 출입구와 빈 바닥 위로만 다닐 수 있고 침대 위로는 다닐 수 없습니다. 어떤 침대가 사용 가능하다는 것은, 출입구에서 출발해 출입구와 빈 바닥 칸만 밟고 걸어서 그 침대와 상하좌우로 인접한 어떤 칸에 도달할 수 있다는 뜻입니다. 모든 침대가 사용 가능한 배치도만 유효한 배치도입니다.

방의 모든 유효한 배치도 중에서 놓을 수 있는 침대의 최대 개수를 구하세요.

첫째 줄에 정수 $T$ ($1 \le T \le 100$), 즉 도미토리의 개수가 주어집니다.

이어지는 $T$개의 줄에는 각각 두 정수 $l$과 $w$ ($1 \le l, w \le 8$)가 주어지며, 이는 한 도미토리의 행 수와 열 수입니다.

각 도미토리마다 한 줄에 정수 하나를 출력합니다. 이는 $l \times w$ 크기의 방의 유효한 배치도가 가질 수 있는 침대의 최대 개수입니다.