Description

不知是从哪里来的消息，听说 ACM 集训队要组织一场气球聚会。届时，会场会有 n 个气球。我们假定所有的气球都是圆的，它们将排成一排，放在同一桌面上。

聚会刚开始的时候，气球都没有充气，此时，我们认为，它们的半径为零。不过很快它们会被从左至右依次充气。当第 i 个气球慢慢变大的时候，它始终与桌面相切，且切点横坐标始终为 xi 。但是气球不能吹得无限大，每个气球有一个半径上限 ri ，当气球碰到其他气球的时候，或者达到半径上限的时候，就应该停止充气。

那么，你的任务就是：计算出充完气后，每个气球的半径。

交这题的同学尽量使用 VC 编译器，否则可能由于编译器差异会得到 Wrong Answer 。

Input

输入的第一行包含一个整数 c ，表示测试数据的组数。 每组数据的第一行包含一个整数 n （1 <= n <= 1000）。 接下来 n 行，第 i 行包含两个整数：xi，ri（0 <= xi <= 100000, 1 <= ri <= 100000）。

Output

每组数据输出 n 行，第 i 行表示第 i 个气球的半径，保留 3 位小数。在每组数据后输出一个空行。

Sample

Input

2
1
0 9
3
0 9
8 1
13 7

Output

9.000

9.000
1.000
4.694

Hint

图中显示的是第二组样例数据的情况。

Source: ycc