Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Điện nguyên tử là bước tiến lớn trong ngành năng lượng, mặc dù tỉ lệ rủi ro là khá cao. Tại vùng đất Highland, có hai nhà máy điện nguyên tử hoạt động đồng thời. Để đảm bảo cuộc sống cho người dân, chính quyền cấp cho mỗi hộ dân nằm trong vùng nguy hiểm những thiết bị đặc biệt để chống ô nhiễm phóng xạ. Mỗi hộ gia đình nằm trong vùng nguy hiểm bán kính R1 từ nhà máy I sẽ nhận được 1 thiết bị bảo vệ, tương tự mỗi hộ gia đình nằm trong vùng nguy hiểm R2 từ nhà máy II cũng nhận được 1 thiết bị.

Tuy nhiên, các gia đình sống ở khu vực mức độ rủi ro thấp lại không có thiết bị bảo vệ. Vì vậy, các gia đình có 2 thiết bị bảo vệ đã chia sẻ bớt 1 thiết bị cho gia đình nào chưa có.

Nhiệm vụ của bạn là đếm xem có bao nhiêu hộ gia đình sẽ không có thiết bị bảo vệ nào?

Hai nhà máy và các hộ gia đình đều nằm trên mặt phẳng với hệ tọa độ Descartes vuông góc Oxy , trong đó khoảng cách giữa hai điểm (x1, y1) và (x2, y2) được tính theo công thức:

√(x1 – x2 )^2 + (y1 – y2 )^2

Bán kính vùng nguy hiểm thay đổi theo thời gian. Cho q trường hợp, mỗi trường hợp sẽ có bán kính vùng nguy hiểm khác nhau.

Trong hình vẽ trên, hai ngôi nhà có tọa độ (81,49) và (77,33) nằm trong vùng nguy hiểm của cả 2 nhà máy điện nguyên tử.

Input

Gồm nhiều bộ test. Mỗi bộ test gồm:

* Dòng 1 chứa số nguyên dương N (0 < N ≤ 200000) là số hộ gia đình.

* n dòng tiếp, dòng I chứa hai số nguyên là tọa độ x_i, y_i (0 ≤ x_i, y_i ≤ 20000) của một hộ gia đình.

* Dòng n+2 chứa 5 số nguyên ax, ay, bx, by và q (0 ≤ ax, ay, bx, by ≤ 20000, 0 <q ≤ 20000). Trong đó tọa độ của nhà máy thứ nhất (ax, ay), tọa độ của nhà máy thứ hai (bx, by) và số trường hợp q.

* q dòng tiếp theo, dòng thứ j chứa hai số nguyên R1,R2 (0 < R1, R2 ≤ 13000) lần lượt là bán kính nguy hiểm của nhà máy thứ nhất và bán kính nguy hiểm của nhà máy thứ hai trong trường hợp thứ j.

 Input kết thúc bởi số 0.

Output

Với mỗi test, dòng 1 in ra số thứ tự của test, q dòng tiếp theo, dòng thứ j ghi một số nguyên duy nhất là số hộ gia đình chưa có thiết bị bảo vệ.

Example

Input:
11
95 75
27 6
93 5
124 13
34 49
65 61
81 49
77 33
110 50
91 22
110 25
57 42 97 36 2
31 25
25 25
0

Output:
Case 1:
2
2