게임

페티아가 바샤에게 새로운 게임을 추천했다. 바샤는 이 게임을 아주 좋아해서 페티아를 이기고 싶어 한다.

게임은 레벨, 방, 그리고 방 사이의 단방향 복도로 이루어진 시스템이다. i번째 레벨에는 1부터 i까지 번호가 붙은 방이 정확히 i개 있고, 각 방에서 복도가 정확히 두 개 나온다. i번째 레벨에서 번호가 j인 방에서 나오는 복도는 i+1번째 레벨의 j번 방과 j+1번 방으로 이어진다. 각 복도에는 길이가 있다. 게임의 목표는 첫 번째 레벨의 유일한 방에서 시작해 마지막 레벨까지 최소 거리로 도달하는 것이다.

바샤는 다음과 같은 전략을 선택했다. 방에 있을 때 그는 그 방에서 나오는 더 짧은 복도를 따라 달린다. 복도의 길이가 같으면 무작위로 같은 확률로 어느 복도를 따라 달릴지 선택한다.

바샤는 같은 지도에서도 무작위 선택에 따라 첫 번째 레벨에서 마지막 레벨까지의 경로 길이가 달라질 수 있다는 것을 알아냈다. 그는 자신의 경로 길이의 기댓값을 구하려고 한다.

확률 변수의 기댓값 정의를 상기하자. 변수가 여러 값을 가지며, 값 xk를 확률 pk로 가진다고 하자. 그러면 기댓값은 x1p1 + x2p2 + ... + xk**pk + ... (가능한 모든 값에 대한 합)이다.

첫 번째 줄에는 입력 데이터의 테스트 예시 개수인 자연수 t가 주어진다. 그다음에 테스트 설명이 이어진다.

각 테스트 설명은 n+1개의 줄로 이루어진다. 첫 번째 줄에는 정수 n (1 ≤ n ≤ 1000)이 주어지며, n+1은 지도의 레벨 수이다.

그다음에 레벨 설명이 이어진다. i번째 줄에는 2i개의 정수가 주어진다. 수는 쌍으로 주어지며 복도의 길이를 나타낸다. j번째 쌍은 다음 레벨의 j번 방과 j+1번 방으로 가는 복도의 길이를 각각 나타낸다. 복도의 길이는 10^9을 넘지 않는다.

모든 테스트에서 n의 합은 1000을 넘지 않는다.

각 테스트마다 별도의 줄에 경로 길이의 기댓값을 출력한다. 답의 상대 오차 또는 절대 오차는 10^-6 이하여야 한다.