잔디 깎기

미르코는 가족이 살 집을 지을 땅을 사려고 한다. 지금까지 본 땅은 K개이고, 각 땅은 N행 M열짜리 직사각형이라서 칸은 모두 $N \times M$개다.

집을 짓기 전에도 땅은 계속 관리해야 하고 잔디도 깎아야 해서, 미르코는 잔디깎이를 한 대 샀다. 잔디를 전부 깎으려면 $N \times M$개 칸을 모두 한 번 이상 지나가야 한다. 미르코는 아무 칸에서나 시작할 수 있고, 시작할 때 위, 아래, 왼쪽, 오른쪽 중 한 방향을 바라본다. 잔디깎이는 바라보는 방향으로 한 칸 전진하거나 제자리에서 90도 회전하는 동작만 할 수 있다. 안전을 위해 미르코는 자기 땅 밖으로 나가지 않으므로 잔디깎이는 항상 직사각형 안에 머문다.

잔디깎이를 회전시키는 일은 힘들어서 미르코는 회전 횟수를 최소로 줄이고 싶다. 땅마다 잔디를 전부 깎는 데 필요한 회전 횟수의 최솟값을 구하라.

첫째 줄에 땅의 개수 K ($1 \le K \le 50000$)가 주어진다.

다음 K개 줄에는 땅 하나의 행 개수 N과 열 개수 M ($1 \le N, M \le 1000000$)이 공백을 사이에 두고 주어진다.

땅마다 잔디를 전부 깎는 데 필요한 회전 횟수의 최솟값을 한 줄에 하나씩 출력한다.

행이 하나뿐인 땅은 회전할 필요가 없다. 첫째 열의 칸에서 오른쪽을 보고 시작해 끝까지 직진하면 된다. 열이 하나뿐인 땅도 마찬가지다.