You are given the coordinates of N cities (x_i, y_i). Each city also has a popularity value, p_i. 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 = |x_i - x|^p_i + | y_i - y |^p_i

Input

The first line contains the number of test cases.

Each test case starts with the number N, the number of points. This is followed by the descriptions of each in the format x_i y_i p_i. The input consists of only integers.

Output

For each test case, 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

Number of test cases ≤ 10
N ≤ 10⁵
|x_i, y_i| ≤ 1000
0 ≤ p_i ≤ 3