탁구공

커다란 방에 쥐덫들이 격자 형태로 배치되어 있다. 각 쥐덫에는 탁구공 두 개가 실려 있으며, 쥐덫이 작동하면 공들이 튀어나가 다른 쥐덫에 떨어져 그 쥐덫을 작동시키도록 조심스럽게 배치되어 있다. 방의 벽은 끈적이므로 방의 벽에 부딪힌 공은 사실상 흡수된다.

공에 맞은 모든 쥐덫은 두 탁구공을 같은 방식으로 내보낸다. 공의 움직임은 공을 내보내는 쥐덫을 기준으로 한 X 변위와 Y 변위로 결정된다. 이제 탁구공 하나를 방 안으로 쏘기로 한다. 이 공은 쥐덫 하나에 맞아 그 쥐덫을 작동시키고, 쥐덫에 있던 공 두 개를 내보낸다. 이 두 공은 다시 쥐덫 두 개를 더 작동시키고, 이제 공 네 개가 날아간다... 모든 움직임이 끝나면 많은 쥐덫이 작동하지만, 날아다니는 모든 공을 피한 쥐덫도 일부 있다.

작동하는 쥐덫의 개수를 계산해야 한다.

예를 들어 첫 번째 예제 테스트 케이스를 보면, 아래 그림은 너비가 5, 높이가 3인 방을 나타낸다. 각 쥐덫에서 탁구공이 날아가는 두 방향은 각각 (-1, 0)와 (-1, -1)이다. 처음 쏜 공은 위치 (4, 2)에 있는 쥐덫에 맞는다. 최종적으로 쥐덫 12개가 작동한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ C ≤ 100 -20 ≤ 모든 변위 ≤ 20 어느 벡터도 길이가 영이 아니다.

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ W, H ≤ 100

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ W, H ≤ 1000000

입력의 첫 줄에는 테스트 케이스의 개수 C가 주어진다. 이어서 C개의 테스트 케이스가 주어진다. 각 테스트 케이스는 네 줄로 이루어진다. 첫 줄에는 쥐덫 격자의 크기(방의 크기와 같음)가 너비 W와 높이 H로 주어진다. 이어지는 두 줄에는 두 탁구공의 도착 지점이 X 변위와 Y 변위로 주어진다. 예를 들어 두 줄이 0 1와 1 1라면, 쥐덫 하나가 작동할 때 공 두 개가 발사된다. 하나는 작동한 쥐덫 바로 위의 쥐덫에 맞고, 다른 하나는 작동한 쥐덫의 위쪽이면서 오른쪽에 있는 쥐덫에 맞는다. 마지막 줄에는 처음 쏜 탁구공으로 작동한 쥐덫의 열과 행을 각각 나타내는 두 정수가 주어진다. 여기서 0 0은 왼쪽 아래의 쥐덫이다.

각 테스트 케이스마다 "Case #A: B"을 포함하는 한 줄을 출력한다. 이때 A는 1부터 시작하는 테스트 케이스 번호이고, B는 작동한 쥐덫의 개수이며 처음 작동한 쥐덫도 이에 포함한다.