러시안 테이블은 행의 길이가 n이고, 열의 길이가 m이며 (r,c) 칸의 값은 (r - 1) \cdot m + c인 이차원 배열로 나타낼 수 있다.

n=3, m=5인 러시안 테이블은 아래와 같이 구성된다.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15

우리는 이 러시안 테이블을 수직 혹은 수평으로 한 번 나눠서 나뉜 양쪽 테이블의 합이 최대한 균등하도록 하고싶다.

예를 들어 위와 같은 테이블에서는 4번째 열의 왼쪽을 수직으로 나누면 왼쪽 테이블의 합은 1+2+3+6+7+8+11+12+13=63이고, 오른쪽 테이블의 합은 4+5+9+10+14+15=57로 이보다 더 차이가 적게 나누는 방법은 없다.

이런 경우 우리는 "V 4"로 테이블을 나눴다고 한다.

각 t개의 테스트 케이스 별로 n과 m이 주어졌을 때, 어떻게 잘라야 최대한 나뉜 두 테이블의 합이 균등할지 출력하시오.

러시안 테이블 timer 1s memory 512MB

러시안 테이블 1s 512MB