405365: GYM101915 J The Volcano Eruption

Memory Limit:64 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. The Volcano Eruptiontime limit per test5 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

"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 ith hole is a circle whose center is at coordinates (xi, yi) and has a radius of ri. 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?

Input

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 ≤ 109) Each of the following N lines contain 3 integers (0 ≤ xi ≤ W), (0 < yi < L), and (1 ≤ ri ≤ 109), the coordinates and radius of the ith 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).

Output

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.

ExampleInput
1
5 5 18
4 2 1
2 12 3
4 6 2
2 6 1
1 7 1
Output
2
Note

The figure below shows a possible solution for the sample.

加入题单

上一题 下一题 算法标签: