문제

체스를 좋아하는 성현이는 기물 중 나이트를 가장 좋아한다! 나이트가 너무나도 좋은 나머지, 자신이 갖고 있는 다른 기물과 친구들이 갖고 있는 나이트를 모조리 교환하여 나이트만 무려 ~10^{100}~개나 갖고 있는 경지에 이르렀다!

나이트는 몹시 공격적이라, 체스판 위에 서로 공격할 수 있는 위치에 놓인 나이트들은 서로가 서로를 잡아먹어 버린다! 성현이는 N \times M 크기의 체스판에 나이트를 서로 공격하지 않도록 배치하고 싶다. 최대 몇 개의 나이트를 배치할 수 있을까?

입력

첫째 줄에 테스트 케이스의 수 T 가 주어진다. (1 ≤ T ≤ 10,000)

각 테스트 케이스의 첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 10,000)

출력

배치할 수 있는 나이트의 최댓값을 출력한다.

예제 입력 1

2
2 4
1 1

예제 출력 1

4
1