Una vez Wendy estaba de tan buen humor que decidió ayudar a su madre con el lavavajillas. Había N platos sucios en el lavadero. Desde el punto de vista geométrico cada plato se parece a un cono romo. Esto sin tener en cuenta la anchura de las paredes del plato y del fondo del mismo. Wendy pone los platos limpios uno sobre otro de forma natural, es decir, de manera que sus ejes verticales coinciden como se ve ne la imagen.

A continuación se le da el orden en el que Wendy lava los platos y los va colocando sobre la mesa. Su tarea será determinar la altura que alcanzan los platos al finalizar con el lavado. Es decir, la distancia desde la parte inferior del plato más bajo hasta la parte superior del plato más alto.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

La primera línea de entrada contiene entero N ( 1 ≤ N ≤ 3000 ). Cada uno de los siguientes N líneas contienen 3 enteros h, r y R ( 1 ≤ h ≤ 10000, 1 ≤ r < R ≤ 10000 ). Estos son la altura de un recipiente, el radio de su parte inferior y el radio de su parte superior.

Los platos se dan en el orden que Wendy los pone sobre la mesa.

Output

Salida para cada caso. La altura de la pila de platos, se permite un error de precisión de al menos 10 ^ -6. Pero para fines prácticos imprimir solo el valor entero del resultado.

Entrada de ejemplo