문제

나이트는 직선으로 두 칸 이동 후, 옆으로 한 칸 이동하며, 이때 이동 과정에 있는 다른 기물을 뛰어넘을 수 있다.

체스를 좋아하는 성현이는 기물 중 나이트를 가장 좋아한다! 나이트가 너무나도 좋은 나머지, 자신이 갖고 있는 다른 기물과 친구들이 갖고 있는 나이트를 모조리 교환하여 나이트만 무려 $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