Minimum Circle Boundary Crossings

Given n circles that are guaranteed to be non-intersecting and non-tangent, and two distinct points \((x_1,y_1)\) and \((x_2,y_2)\) (neither of which lies exactly on any circle), determine the minimum number of circle boundaries that any continuous curve from \((x_1,y_1)\) to \((x_2,y_2)\) must cross.

A point is considered inside a circle if its Euclidean distance from the circle's center is strictly less than the circle's radius. Since the circles do not intersect or touch each other, the only boundaries that must be crossed are those for which one of the points lies inside the circle and the other lies outside.

The answer is the number of circles for which exactly one of the two points is inside.

Mathematically, for a circle with center \((c_x,c_y)\) and radius \(r\), define the indicator function:

[ I(P) = \begin{cases} 1, & (x_P - c_x)^2+(y_P-c_y)^2 < r^2 \ 0, & \text{otherwise} \end{cases} ]

Then the total number of boundary crossings is:

[ \sum_{i=1}^{n} \left| I_{i}(x_1,y_1) - I_{i}(x_2,y_2) \right| ]

</p>

inputFormat

The input begins with an integer T representing the number of test cases.

Each test case is described as follows:

1. A line containing four space‐separated integers: x1 y1 x2 y2, denoting the coordinates of the starting and ending points.
2. A line containing an integer n, the number of circles.
3. Then n lines follow, each containing three space‐separated integers cx cy r, representing the center and radius of a circle.

It is guaranteed that for any circle, neither of the two points lies exactly on its boundary, and that any two circles do not intersect or touch.

outputFormat

For each test case, output a single line with an integer representing the minimum number of circle boundaries the curve must cross.

sample

3
0 0 10 0
2
2 0 3
8 0 3
1 1 2 2
2
0 0 2
10 10 5
1 1 2 2
1
5 5 2

2
1
0

</p>