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

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

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

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

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

Input

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

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

Output

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

Examples

Input 1

2
5 5 1 1
6 6 1 2

Output 1

15
24