자리 배치 (Large)

게임 세계 챔피언십 개막식이 열린다. 선수는 $R$개의 행과 $C$개의 열로 이루어진 격자 모양 좌석에 앉는다.

경쟁이 치열해서 선수는 앞으로 맞붙을 상대가 바로 옆에 앉는 것을 불편해한다. 어떤 선수의 바로 왼쪽 자리와 바로 오른쪽 자리에 모두 다른 선수가 앉으면 그 선수는 답답함을 느낀다. 바로 앞자리와 바로 뒷자리에 모두 다른 선수가 앉아도 답답함을 느낀다.

답답함을 느끼는 선수가 한 명도 없도록 앉힐 때, 앉힐 수 있는 선수 수의 최댓값을 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 $R$와 $C$로 이루어진 한 줄이다. $R$는 좌석의 행 수, $C$는 좌석의 열 수다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 답답함을 느끼는 선수가 없도록 앉힐 수 있는 선수 수의 최댓값이다.

• $1 \le T \le 100$
• $1 \le R \le 100$
• $1 \le C \le 100$

$R = 2$, $C = 2$이면 네 자리를 모두 채워도 답답함을 느끼는 선수가 없다.

$R = 2$, $C = 3$이면 한 행에 세 명을 앉힐 수 없다. 가운데 선수가 답답함을 느끼기 때문이다. 앞의 두 열을 가득 채우면 네 명이 앉고, 이보다 많이 앉히는 방법은 없다.

$R = 4$, $C = 1$이면 첫 두 행과 마지막 행을 채우는 배치가 최적이고, 세 명이 앉는다.