초콜릿과 친구들의 습격

코코의 초콜릿 기계는 가로와 세로가 4의 배수인 직사각형 모양의 초콜릿을 생산한다. 코코는 이 기계에서 생산된 $M \times N$ 크기의 초콜릿을 $1 \times 2$ 또는 $2 \times 1$ 크기로 나누어 판매하려고 한다. 하지만 어느 날 코코의 친구 $K$명이 놀러 와서 $1 \times 1$ 초콜릿 한 칸씩을 떼어 먹어 버렸다. 남은 초콜릿을 나누었을 때 최대 몇 개의 초콜릿을 얻을 수 있는지 코코에게 알려주자.

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 그 다음 줄부터 $T$개의 테스트 케이스가 순서대로 주어진다. ($1 \le T \le 1000$)

각 테스트 케이스의 첫 줄에는 $M$, $N$, 의 값이 주어진다. 은 초콜릿의 가로의 길이, 은 세로의 길이이다. (, 은 의 배수, )

각 테스트 케이스에 대해, 주어진 초콜릿을 나누어 얻을 수 있는 $1 \times 2$ 또는 $2 \times 1$ 초콜릿의 개수의 최댓값을 한 줄에 출력한다.