Traveling Cellsperson

• 그리드에서 S의 위치는 답에 영향을 주지 않는다. 그리드의 크기만 중요하다.
• 그리드 그래프는 R또는 C가 짝수이면 해밀턴 사이클을 갖는다. 해밀턴 사이클을 따라서 이동한다면, 모든 노드를 방문하고 돌아오는 이동 거리는 노드 개수만큼이 된다. 즉 답은 R*C
• R과 C가 3이상인 홀수일 경우에는, 그래프에서 노드 하나를 제거해서 해밀턴 그래프로 만들수가 있다. 이 위에서 해밀턴 사이클을 따라 이동하고, 제거한 노드 옆을 지나갈때만 그 노드를 방문하고 돌아오면 된다. 이동거리는 R*C-1 + 2 = R*C+1 이 된다
• R=1일 때에는, 시작 노드에서 한쪽 끝까지 갔다가 다른쪽 끝까지 갔다가 다시 시작 노드로 돌아와야 한다. 이동거리는 (C-1)*2.
  • C=1 일때도 마찬가지로 구한다.

"""Solution code for "BOJ 11164. Traveling Cellsperson".

- Problem link: https://www.acmicpc.net/problem/11164
- Solution link: http://www.teferi.net/ps/problems/boj/11164

Tags: [ad hoc]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        X, Y = [int(x) for x in sys.stdin.readline().split()]
        # pylint: disable-next=unused-variable
        grid = [sys.stdin.readline().rstrip() for _ in range(Y)]

        if X == Y == 1:
            print('0')
        elif X == 1 or Y == 1:
            print((max(X, Y) - 1) * 2)
        elif X % 2 == Y % 2 == 1:
            print(X * Y + 1)
        else:
            print(X * Y)

    print('LOL')


if __name__ == '__main__':
    main()