SP418 NECKLACE - Necklace

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} $** ) _$ ^{2} $_ + (**y** - **y $ _{i} $** ) _$ ^{2} $_ ≤ **r $ _{i} $** _$ ^{2} $_ , 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.

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.

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} $** ) _$ ^{2} $_ + (**y $ _{i} $** - **y $ _{j} $** ) _$ ^{2} $_ ) in the rules above.