문제
조이는 쉬는시간을 즐기기 위해 n행 m열로 놓여있는 책상 위를 뛰어다니고 있다.
조이가 책상 위를 뛰어다니는 데에는 자신만의 규칙이 있다. 먼저 한 책상 위로 올라가 뛰어갈 방향을 정한다.
그 뒤, 조이는
(1) 바라보는 방향으로 뛰어가던가,
(2) 바라보는 방향을 90도만큼 회전할 수 있다.
방향은 상하좌우만 가능하다.
목표는 모든 책상을 한 번 이상 지나는 것이다.
조이는 책상을 뛰어다닐 때, 방향을 바꾸는 것이 너무 힘들었다. 그
래서 방향을 바꾸는 횟수를 최소로 하는 방법을 찾아보기로 했다.
하지만, 조이는 횟수의 최솟값을 알 수 없었다.
조이를 도와 모든 책상을 한 번 이상 지나면서, 방향을 바꾸는 횟수의 최솟값을 구해주자.
입력
첫 번째 줄에 테스트케이스의 개수 T가 주어진다. (1≦T≦50000)
두 번째 줄부터 T개의 줄에 교실의 크기를 나타내는 자연수 n, m이 공백을 사이에 두고 주어진다. (1≦n, m≦10^6)
출력
T개의 줄에, 각 테스트케이스별로 회전 횟수의 최솟값을 출력한다.
예제 #1
2
10 1
1 10
0
0
예제 #2
3
3 4
1 1
3 3
4
0
4
예제 #3
2
6 4
5 8
6
8
힌트
출처
COCO 2017/2018, , 2018camp contest5 problemB
로그인해야 코드를 작성할 수 있어요.