유스호스텔 도미토리

시간 제한1초메모리 제한128 MB

요약

l x w 격자에서 경계에 있는 입구 하나로부터 바닥 칸을 통해 모든 침대에 도달할 수 있도록 배치할 때 놓을 수 있는 침대의 최대 개수를 구하는 문제입니다.

난이도: 보통10점 중 6점
유형: 조합론, 그리디, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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

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

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

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

입력

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

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

출력

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

예제4

예제 1
입력
```
3
1 1
4 7
3 8
```
예상 출력
```
0
16
16
```
예제 2
입력
```
1
1 1
```
예상 출력
```
0
```
예제 3
입력
```
2
1 8
8 1
```
예상 출력
```
2
2
```

예제 4

입력

예상 출력