You are given the coordinates of N cities (xi,yi). Each city also has a popularity value, pi. You have to place a new city (x,y) such that the sum of distances of this new point from all the other given points is minimized.
Distance of the new point from a given city i is given by :
d = |xi - x| ^ pi + | yi - y | ^ pi

Input

There are multiple test cases.
First line contains the number of testcases.
Each testcases starts with the number N, the number of points.
This is followed by the descriptions of each in the format
xi yi pi
The input consists of only integers

Output

For each testcase, output the minimum distance obtained, with exactly 3 digits after the decimal point.

Example

Input:
1 
3 
1 2 0 
4 5 1 
2 4 2
Output:
4.500

Constraints

No. of testcases <= 10
N <= 10^5
|xi,yi| <= 1000
0 <= pi <= 3