초콜릿과 ㄱ나이트 게임 (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)$

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