시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB46016314035.264%

문제

가로 크기 $W$, 세로 크기 $H$의 직사각형이 $WH$개의 $1\times 1$ 크기의 단위 정사각형으로 나누어져 있다. 이 직사각형에 다음의 행동을 원하는 만큼 반복할 수 있다.

  • 남아있는 단위 정사각형 중에서 정확히 한 개를 제거한다. 이때 남아있는 도형 전체의 둘레의 길이가 바뀌면 안된다. 도형이 여러 개로 나누어지는 것은 허용된다.

이때, 제거한 단위 정사각형의 개수를 최대화하는 방법을 아무거나 하나 찾아 출력하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1\le T\le 1000$)

각 테스트 케이스에 대해, 직사각형의 가로 크기 $W$와 세로 크기 $H$가 한 줄에 공백으로 구분하여 주어진다. ($1\le W,H\le 1000$)

모든 테스트 케이스의 $W\times H$의 합은 $1 000 000$을 초과하지 않는다.

출력

각 테스트 케이스에 대해, 다음과 같이 출력한다.

  • 먼저, 제거한 단위 정사각형의 개수 $n$을 한 줄에 출력한다.
  • 그 다음 줄부터 $n$줄에 걸쳐서, 제거할 단위 정사각형의 위치를 제거되는 순서대로 한 줄에 하나씩 출력한다. 하나의 정사각형의 위치는 $x$좌표와 $y$좌표의 순서로 공백으로 구분하여 출력한다. 맨 왼쪽 위 칸의 좌표는 $(1,1)$이고, 맨 오른쪽 아래 칸의 좌표는 $(W,H)$이다.

예제 입력 1

2
2 2
1 3

예제 출력 1

2
2 1
1 2
1
1 2

출처

Contest > BOJ User Contest > 피갤컵 > 제3회 피갤컵 E번