22067번 - Игра 스페셜 저지다국어

문제

Петя посоветовал Васе новую игру. Эта игра очень понравилась Васе, и он захотел выиграть у Пети.

Игра представляет собой систему уровней, комнат и односторонних коридоров между ними. На i-м уровне ровно i комнат, пронумерованных от 1 до i, из каждой комнаты выходит ровно два коридора. Коридоры из комнаты на i-м уровне, имеющей номер j, ведут на уровень с номером i + 1 в комнаты с номерами j и j + 1. Каждый коридор имеет свою длину. Цель игры заключается в том, чтобы, начав в единственной комнате первого уровня, дойти до последнего уровня, преодолев минимальное расстояние.

Вася выбрал следующую стратегию в игре. Находясь в комнате, он бежит по более короткому коридору, ведущему из неё. Если же длины коридоров одинаковые, то он случайным образом равновероятно выбирает, по какому коридору побежать.

Вася заметил, что на одной и той же карте длина пути от первого уровня до последнего у него может быть разной, в зависимости от его случайных выборов. Он хочет посчитать математическое ожидание длины его пути.

Напомним определение математического ожидания случайной величины. Пусть величина принимает различные значения, причем значение x_k принимается с вероятностью p_k. Тогда математическим ожиданием называется сумма x₁p₁ + x₂p₂ + ... + x_kp_k + ... (сумма берется по всем возможным значениям).

입력

Первая строка содержит одно натуральное число t — число тестовых примеров во входных данных. Далее следуют описания тестов.

Описание каждого теста состоит из n + 1 строки. Первая строка содержит одно целое число n (1 ≤ n ≤ 1000), где n + 1 — число уровней на карте.

Далее следует описание уровней, i-я строка содержит 2i целых чисел. Числа идут по парам и описывают длины коридоров, j-я пара чисел задает длины коридоров в комнаты j и j + 1 на следующем уровне, соответственно. Длины коридоров не превышают 10⁹.

Сумма n по всем тестам не превосходит 1000.

출력

Для каждого теста в отдельной строке выведете матожидание длины пути. Ответ должен иметь относительную или абсолютную погрешность не более 10^-6.

제한

힌트