초콜릿

Bituś와 Bajtuś는 엄마에게서 초콜릿 한 판을 받았다. 초콜릿은 $n \times m$ 크기의 직사각형이며, $n \cdot m$개의 정사각형 조각으로 나뉘어 있다. 둘은 초콜릿을 그냥 절반씩 나누는 대신 새로 생각해 낸 게임을 하기로 했다. 먼저 무작위로 고른 한 조각에 X 표시를 하고, 다음 규칙을 정했다.

• 두 사람은 번갈아 가며 수를 두고, Bituś가 먼저 시작한다.
• 한 번의 수는 조각들을 나누는 (가로 또는 세로) 선 하나를 따라 초콜릿을 쪼갠 뒤, 나뉜 두 조각 중 하나를 먹는 것이다.
• X 표시된 조각을 먹는 사람이 진다.

게임은 무척 흥미진진했고, 결국 Bajtuś의 승리로 끝났다. 아쉬워하던 Bituś는 표시된 칸의 위치가 자신의 패배에 얼마나 영향을 주었는지 궁금해졌다. 그래서 $n \cdot m$개의 조각 중에서, 그 조각에 X를 표시했을 때 Bituś가 지게 되는 조각이 몇 개인지 알고 싶어 한다. 두 사람 모두 최적으로 플레이한다고 가정한다.

첫째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10^4$)가 주어진다. 이어지는 $t$개의 줄에는 각 초콜릿의 크기를 나타내는 두 정수 $n$, $m$ ($1 \le n, m \le 10^9$)이 주어진다.

$t$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 초콜릿에서 어떤 조각에 X를 표시했을 때 Bituś가 지게 되는지, 그러한 조각의 개수를 정수 하나로 출력한다.