You are required to cross a river to reach your destination. The streamflow of the river was fast, therefore, you cannot cross the river by swimming.
The river is available at the X-axis and its boundary is marked by Y coordinates, from y=A to y=B.
--------------------------------------------------------------------------------- (y=A)
..................................................................................................
..................................................................................................
..................................................................................................
---------------------------------------------------------------------------------- (y=B)
You are provided with some rocks along with their centers and radius respectively. Currently, you are standing on the shore y=B. You cannot jump between rocks but can move from one rock to another if both rocks overlap at some point. You are required to determine whether you will be able to cross the river by using rocks or not. If you can cross the river, then print the minimum number of rocks that are required to cross the river. Otherwise, print −1.
Input format
- First line: T denoting the number of test cases
- For each of the test case:
- First line: N denoting the number of rocks
- Second line: N lines containing three integers X,Y,R where (X,Y) denotes the coordinates of the center of that rocks and R denotes its radius
- Third line: Two integers A and B denoting the upper and lower boundary of the river respectively
Output format
Print the required answer in a separate line for each of the test case.
Constraints
1≤T≤10
1≤N≤5000
−109≤X,Y,A,B≤109
1≤R≤109
B<A
At first we can step onto the first rock from the river shore. Then we can cross river directly or can move to second rock and then cross it. Note that we can't use third rock as it is beyond the reach from the other rocks.
