17번 - 정사각형 따먹기

가로 크기 $W$, 세로 크기 $H$의 직사각형이 $WH$개의 $1 \times 1$ 크기의 단위 정사각형으로 나누어져 있다. 이 직사각형에 다음의 행동을 원하는 만큼 반복할 수 있다. \begin{itemize} \item 남아있는 단위 정사각형 중에서 정확히 한 개를 제거한다. 이때 남아있는 도형 전체의 둘레의 길이가 바뀌면 안된다. 도형이 여러 개로 나누어지는 것은 허용된다. \end{itemize} 이때, 제거한 단위 정사각형의 개수를 최대화하는 방법을 아무거나 하나 찾아 출력하시오.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1000$) 각 테스트 케이스에 대해, 직사각형의 가로 크기 $W$와 세로 크기 $H$가 한 줄에 공백으로 구분하여 주어진다. ($1 \le W, H \le 1000$) 모든 테스트 케이스의 $W \times H$의 합은 $1\;000\;000$을 초과하지 않는다.

각 테스트 케이스에 대해, 다음과 같이 출력한다. \begin{itemize} \item 먼저, 제거한 단위 정사각형의 개수 $n$을 한 줄에 출력한다. \item 그 다음 줄부터 $n$줄에 걸쳐서, 제거할 단위 정사각형의 위치를 $x$좌표와 $y$좌표의 순서로 공백으로 구분하여 출력한다. 맨 왼쪽 위 칸의 좌표는 $(1,1)$이고, 맨 오른쪽 아래 칸의 좌표는 $(W,H)$이다. \end{itemize}