31470번 - 초콜릿과 ᄀ나이트 게임 (Bitter)

문제

코코는 가로 길이 $X,ドル 세로 길이 $Y$인 직사각형 모양의 초콜릿을 갖고 있다. 이 초콜릿은 1ドル\times 1$ 크기의 단위 정사각형으로 나누어져 있다.

코코는 이 초콜릿과 여러 개의 ᄀ나이트를 가지고 ᄀ나이트 게임을 하려고 한다. ᄀ나이트는 체스에서 사용하는 나이트의 변형으로, 한 번에 오른쪽이나 왼쪽으로 $x$칸, 위나 아래로 $y$칸 떨어진 칸으로 이동할 수 있다. ᄀ나이트는 이동할 때 다른 칸에 있는 말의 방해를 받지 않는다. 목적지 칸이 초콜릿의 범위를 벗어나는 경우에는 그곳으로 이동할 수 없다.

ᄀ나이트 게임은 초콜릿 위에 다음의 규칙을 지키면서 최대한 많은 ᄀ나이트를 올리는 게임이다.

• 초콜릿의 한 칸에는 최대 하나의 ᄀ나이트를 올릴 수 있다.
• 어떤 ᄀ나이트가 한 번에 이동할 수 있는 칸에 다른 ᄀ나이트가 있으면 안 된다.
• 초콜릿은 뒤집거나 회전할 수 없다.

코코가 초콜릿에 ᄀ나이트를 최대 몇 개까지 올릴 수 있는지 계산해 보자.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 100,円 000)$

각 테스트 케이스에 대해, 초콜릿의 가로 길이 $X,ドル 세로 길이 $Y,ドル ᄀ나이트의 이동 규칙을 나타내는 $x$와 $y$의 값이 한 줄에 공백으로 구분되어 순서대로 주어진다. $(1\le X,Y,x,y\le 10^9)$

출력

각 테스트 케이스에 대해, 초콜릿에 올릴 수 있는 ᄀ나이트의 최대 개수를 한 줄에 출력한다.

제한

힌트