405365: GYM101915 J The Volcano Eruption

"The volcano erupted!". Shouted Shahhoud, as he was attempting to wake Saeed up.

"You need to save Noor, he is trapped in the lab next to the volcano!". Shahhoud said.

You can picture the road between the base and the lab as a rectangle whose bottom left corner is at (0, 0) and top right corner is at (W, L). There are n holes filled with lava from the volcano. The i^th hole is a circle whose center is at coordinates (x_i, y_i) and has a radius of r_i. The holes may intersect to make larger holes.

Saeed Starts his mission at any point on the bottom side of the rectangle ( any point (0...W, 0)), and has to reach any point on the top side of the rectangle ( any point (0...W, L)), in order to save Noor.

None of the holes intersect with the bottom or the top sides of the rectangle ( the starting and finishing line).

Saeed can take special suits in his anti-lava backpack. Each special suit allows him to swim in one or more intersecting holes (once he goes out of the lava onto the street, he has to throw away the suit). Saeed must stay inside the street at all times. Please note that if two holes are touching each other by the border, then Saeed can't walk from between them without wearing a special suit.

What is the minimum number of suits Saeed has to take with him in order to reach the lab and save Noor?

The first line contains a single integer T, the number of test cases. The first line of each test case contains 3 integers N,W, and L. The number of holes, the width, and the length of the rectangle. (1 ≤ N ≤ 1000) (1 ≤ W, L ≤ 10⁹) Each of the following N lines contain 3 integers (0 ≤ x_i ≤ W), (0 < y_i < L), and (1 ≤ r_i ≤ 10⁹), the coordinates and radius of the i^th hole. It's guaranteed that none of the holes intersect with the bottom or the top sides of the rectangle ( the starting and finishing line).

For each test case, output a single line containing a single integer, the minimum number of suits Saeed must take with him to save Noor.

1
5 5 18
4 2 1
2 12 3
4 6 2
2 6 1
1 7 1

2

The figure below shows a possible solution for the sample.