착석

Codejamon 게임의 열기가 뜨겁다! 많은 플레이어가 World Championship을 놓고 겨루기 위해 강당에 모였다. 개회식에서 플레이어들은 R개의 행과 C개의 열로 이루어진 좌석 격자에 앉는다.

경쟁은 치열할 것이며, 플레이어들은 미래의 상대가 너무 많이 가까이 앉는 것에 민감하다! 어떤 플레이어의 바로 왼쪽에 다른 플레이어가 앉고 바로 오른쪽에도 또 다른 플레이어가 앉으면, 그 플레이어는 지나치게 붐빈다고 느낀다. 또한 어떤 플레이어의 바로 앞에 한 플레이어가 앉고 바로 뒤에도 또 다른 플레이어가 앉으면, 그 플레이어는 지나치게 붐빈다고 느낀다.

어떤 플레이어도 지나치게 붐빈다고 느끼지 않도록 앉힐 수 있는 플레이어 수의 최댓값은 얼마인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ R ≤ 5. 1 ≤ C ≤ 5.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ R ≤ 100. 1 ≤ C ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어지고, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 R과 C가 있는 한 줄로 이루어지며, 각각 강당 의자의 행 수와 열 수를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이고(1부터 시작), y은 문제 설명에 명시된 대로 앉힐 수 있는 플레이어 수의 최댓값이다.

예제 케이스 #1에서는 모든 좌석을 채울 수 있으며, 어떤 플레이어도 지나치게 붐빈다고 느끼지 않는다.

예제 케이스 #2에서는 각 행에 좌석이 세 개 있다. 한 행에 플레이어 세 명을 앉히면 가운데 플레이어가 지나치게 붐빈다고 느끼므로 그렇게 할 수 없다. 최적해 중 하나는 처음 두 열을 각각 모두 채워 총 네 명의 플레이어를 앉히는 것이다.

예제 케이스 #3에서 최적해 중 하나는 처음 두 행과 마지막 행을 채워 총 세 명의 플레이어를 앉히는 것이다.