Trong lúc ôn tập phần hình học để thi học sinh giỏi tin học, Hải quan sát mối quan hệ giữa các cung tròn được tạo bởi giao của một số các đường thẳng với một đường tròn như sau:

Cho một đường tròn xác định bởi tọa độ tâm ~(x, y)~, bán kính ~r~ và ~n~ đường cát tuyến, trong đó đường cát tuyến thứ ~i~ được xác định bởi phương trình ~a_i x + b_i y = c_i~. Biết rằng không có đường cát tuyến nào đi qua tâm đường tròn. Một đường cát tuyến nếu cắt đường tròn tại hai điểm ~A~ và ~B~ thì cung ~\widehat{AB}~ nhỏ của đường tròn được gọi là cung đặc trưng của đường cát tuyến đó. Lưu ý: nếu đường cát tuyến tiếp xúc với đường tròn thì cung đặc trưng suy biến thành một điểm.

Tiếp theo, Hải dựng đồ thị đơn vô hướng ~G = (V, E)~, trong đó mỗi đỉnh trong đồ thị tương ứng với một cung đặc trưng của đường tròn, và hai đỉnh trong ~V~ có cạnh nối trong ~E~ khi và chỉ khi hai cung đặc trưng tương ứng của hai đỉnh này có điểm chung.

Gọi hai cạnh khác nhau ~(u_1, v_1)~ và ~(u_2, v_2)~ trong ~E~ là độc lập nếu như không tồn tại đỉnh ~t \in V~ sao cho cả hai điều kiện sau đều đúng:

• Cạnh ~(u_1, t)~ hoặc cạnh ~(v_1, t)~ nằm trong ~E~.

• Cạnh ~(u_2, t)~ hoặc cạnh ~(v_2, t)~ nằm trong ~E~.

Hải muốn tìm ~E'~ là tập con lớn nhất của ~E~ sao cho mọi cặp cạnh trong ~E'~ đều độc lập. Hãy giúp Hải giải bài này nhé!

Input

Dòng thứ nhất chứa số nguyên dương ~T~ (~1 \le T \le 10~) là số lượng bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau:

Dòng đầu tiên chứa ba số nguyên ~x~, ~y~, ~r~ (~|x|, |y|, r \le 10^9~) lần lượt là tọa độ tâm và bán kính của đường tròn.

Dòng thứ hai chứa một số nguyên dương ~n~ (~1 \le n \le 50\,000~) là số lượng đường cát tuyến.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~a_i, b_i, c_i~ (~|a_i|, |b_i|, |c_i| \le 10^9~) là các tham số của đường cát tuyến thứ ~i~.

Dữ liệu đảm bảo là trong số các giao điểm của các đường cát tuyến với đường tròn không có hai điểm nào cách nhau ở khoảng cách nhỏ hơn ~10^{-3}~.

Output

In ra ~T~ dòng, mỗi dòng chứa một số nguyên là số lượng cạnh nằm trong tập độc lập lớn nhất. Nếu không tồn tại cạnh nào, in ra ~-1~.

Scoring

Sample Input 1

1
0 0 5
8
0 1 2
11 3 40
7 -3 29
1 -2 10
-1 -2 9
1 0 -2
-6 7 42
0 1 5

Sample Output 1

2