Giải bài trực tuyến

Microhoo and Googloo are two competing IT companies from the same city. Each company has offices scattered across the city. To protect their critical information from each other, both companies have agreed to locate their headquarters as far from each other as possible.

Given the locations of Microhoo and Googloo existing offices, your task is to write a program to help the two companies to select their headquarters from existing offices so that the distance between their headquarters is longest.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains the integer n (2 ≤ n ≤ 30000) representing the total number of offices for both companies. The ith line of the next n line contains three integers xi, yi, ci (0 ≤ |xi|, |yi| ≤ 10⁸, 0 ≤ ci ≤ 1) separated by space, where (xi, yi) is the coordinate of the ith office and it is Microhoo’s office if ci = 0 and Googloo’s if ci = 1.

It is guaranteed that each company has at least one office.

Output

For each data test, write in one line the integer part of the longest distance between Microhoo’s and Googloo’s headquarters.

Example

Sample Input
2
2
0 0 0
3 -2 1
5
1 5 1 
-5 2 0
3 7 1
6 -2 0 
5 1 0

Sample Output
3
9