Cross the River
Saatwik, an elite programmer love the woods. Once he was in one of his trips to the mighty Himalayas , he encountered a strange problem. As we all know that, Himalayas has abundant river streams and forests. While travelling in one of the forest, he was trapped by the river stream flowing. As the stream flow was fast, he couldn't cross by swimming across water, he must find some other way to cross it.
River is present throughout the X axis and its boundary is marked by y coordinates (i.e. from y=A to y=B) .
--------------------------------------------------------------------------------- (y=A)
..................................................................................................
..................................................................................................
..................................................................................................
---------------------------------------------------------------------------------- (y=B)
Now, You are provided with some rocks along with their centres and radius respectively. Currently Saatwik is present on the shore having y=B . We can't jump between the rocks but we can move from one rock to other if both overlap at some points. You need to tell whether Saatwik will be able to cross the river by using any number of rocks or not . If he can, then output the minimum number of rocks taken to achieve it otherwise output −1
Input :
First line of input will contain T denoting number of test cases. For each of the test cases, First line will contain N denoting number of rocks. From second line onward, there will be N lines containing 3 integers X,Y,R where (X,Y) denotes the coordinates of the centre of that rocks and R stands for its radius. Last line will contain two integers A and B denoting the upper and lower boundary of the river respectively.
Output:
Output 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
Sample Input
1
3
1 1 2
1 2 1
3 4 1
3 0
Sample Output
1
Explanation
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.
Time Limit: 2.0 sec(s) for each input file
Memory Limit: 256 MB
Source Limit: 1024 KB