산장

헥토르가 HektorJudge 프로젝트를 진행하는 동안, 그의 동료 빅토르는 인생이 컴퓨터 앞에 앉아 있는 것만으로 이루어져서는 안 된다고 생각하고 산으로 여행을 떠났다. 저녁에 산장에 도착한 빅토르는 주말을 산에서 보내려는 사람이 자기 혼자만이 아니라는 사실에 놀랐다. 산장은 관광객으로 가득 차 있었다!

이 곤란한 상황에서 산장 관리인은 관광객들이 산장 중앙 홀 바닥에서 잘 수 있도록 자리를 마련해야 했다. 홀은 $W$개의 행과 $K$개의 열로 배열된 $W \times K$개의 정사각형 칸으로 이루어진 직사각형이다. 각 관광객은 서로 인접한(가로 또는 세로로 맞닿은) 정확히 두 칸을 차지한다. 각 칸이 최대 한 명의 관광객에게만 쓰이도록 할 때, 주어진 크기의 홀에 최대 몇 명의 관광객을 배치할 수 있는가? 수학과 컴퓨터에 능한 빅토르는 곧바로 정확한 답을 계산해 냈다.

첫 번째 줄에는 테스트 세트의 개수를 나타내는 자연수 $Z$ ($1 \le Z \le 10$)가 주어진다. 이어서 각 테스트 세트가 차례로 주어진다.

각 테스트 세트는 한 줄로 이루어지며, 공백 하나로 구분된 두 양의 정수 $W$와 $K$ ($1 \le W, K \le 1000$)를 담고 있다.

각 테스트 세트마다, 산장 홀에서 동시에 잘 수 있는 관광객의 최대 수를 한 줄에 하나씩 출력한다. 출력하는 답의 순서는 입력에 주어진 테스트 세트의 순서와 일치해야 한다.