Online Programming Server

In Byteland, machine communicate via wireless technology. Therefore, there are many radio towers installed
in Byteland. Limited by power supply, each tower has its maximum transmit distance, denoted by r_i.
We say two tower i and j can communicate directly if their distance between them is no larger than r_i and r_j . The distance here is defined as euclidean distance, which is
((x_i + x_j)² + (y_i + y_j)²)^0.5. Two towers
i and j can communicate if they can communicate directly, or there exists a tower k such that i and k can
communicate and k and j can communicate.
Alice and Bob wants to communicate. Lets assume Alice is located at tower 1 and Bob is located at tower
N. They are going to choose a subset of tower such that 1 and N can communicate. Moreover, they hope that the subset can be as small as possible because they are afraid that the message will be overheard by someone.

The first line contain an integer T(1 ≤ T ≤ 20), the number of test cases.
For each test cases, the first line contains an integer N (2 ≤ N ≤ 500), the number of towers.
Followed by N lines, each lines contains 3 integers x_i, y_i, r_i (0 ≤ x_i, y_i, r_i ≤ 10000).

The position of all towers are distinct.

For each test cases, output the minimum tower involved (including tower 1 and N). If it is impossible for them to communicate, output -1.