There are N points marked on a surface, pair (x_i, y_i) is coordinates of a point number i. Let's call a necklace a set of N figures which fulfills the following rules.

• The figure #i consists of all such points (x, y) that (x - x_i)² + (y - y_i)² ≤ r_i², where r_i ≥ 0.
• Figures #i and #(i+1) intersect (1 ≤ i < N).
• Figures #1 and #N intersect.
• All the rest pairs of figures do not intersect.

Write a program which takes points and constructs a necklace.

Input

First line of input contains an integer t (1 ≤ t ≤ 45), equals to the number of testcases. Then descriptions of t testcases follow.

The first line of the description contains one integer number N (2 ≤ N ≤ 100). Each of the next N lines contains two real numbers x_i, y_i (-1000 ≤ x_i, y_i ≤ 1000), separated by one space. It is guaranteed that at least one necklace exists for each testcase.

Output

For each testcase your program should output exactly N lines. A line #i should contain real number r_i (0 ≤ r_i < 10000). To avoid potential accuracy problems, a checking program uses the following rules.

• Figures #i and #j definitely do not intersect if r_i + r_j ≤ d_ij - 10^-5.
• Figures #i and #j definitely intersect if d_ij + 10^-5 ≤ r_i + r_j.
• The case when d_ij - 10^-5 < r_i + r_j < d_ij + 10^-5 is decided in favour of a contestant.
• d_ij equals sqrt((x_i - x_j)² + (y_i - y_j)²) in the rules above.

Example

Input:
1
4
0 0
10 0
10 10
0 10

Output:
7
7
7
7