자리 배치 (작은 입력)

퍼즐 게임 대회의 열기가 뜨겁다. 세계 챔피언 자리를 놓고 겨루려고 많은 선수가 강당에 모였다. 개막식에서 선수들은 $R$개의 행과 $C$개의 열로 놓인 좌석에 앉는다.

경기는 치열하고, 선수들은 앞으로 맞붙을 상대가 곁에 너무 많이 앉는 것을 불편해한다. 어떤 선수의 바로 왼쪽 자리와 바로 오른쪽 자리에 모두 다른 선수가 앉으면 그 선수는 답답함을 느낀다. 바로 앞자리와 바로 뒷자리에 모두 다른 선수가 앉아도 답답함을 느낀다.

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

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 강당 좌석의 행 수 $R$과 열 수 $C$를 나타내는 두 정수가 공백으로 구분되어 적힌 한 줄로 이루어진다.

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

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

예제의 첫 번째 테스트 케이스에서는 모든 자리를 채워도 답답함을 느끼는 선수가 없다.

두 번째 테스트 케이스에서는 한 행에 자리가 세 개다. 한 행을 전부 채우면 가운데 선수가 답답함을 느끼므로 그렇게 앉힐 수 없다. 앞의 두 열을 모두 채우면 네 명이 앉고, 이것이 최적이다.

세 번째 테스트 케이스에서는 첫 두 행과 마지막 행을 채우면 세 명이 앉고, 이것이 최적이다.