Game

Petya recommended a new game to Vasya. Vasya liked the game a lot and wants to beat Petya.

The game is a system of levels, rooms, and one-way corridors between them. Level i has exactly i rooms, numbered from 1 to i, and exactly two corridors leave each room. The corridors leaving room number j on level i lead to level i+1, to rooms numbered j and j+1. Each corridor has its own length. The goal of the game is to start in the only room of the first level and reach the last level covering the minimum distance.

Vasya chose the following strategy. When he is in a room, he runs along the shorter corridor leaving it. If the corridors have equal lengths, he chooses uniformly at random which corridor to run along.

Vasya noticed that on the same map the length of his path from the first level to the last can differ depending on his random choices. He wants to compute the expected value of his path length.

Recall the definition of the expected value of a random variable. Suppose the variable takes various values, with value xk taken with probability pk. Then the expected value is the sum x1p1 + x2p2 + ... + xk**pk + ... (the sum is over all possible values).

The first line contains a single positive integer t, the number of test cases in the input. The descriptions of the tests follow.

Each test description consists of n+1 lines. The first line contains a single integer n (1 ≤ n ≤ 1000), where n+1 is the number of levels on the map.

The description of the levels follows. The i-th line contains 2i integers. The numbers go in pairs and describe corridor lengths. The j-th pair gives the lengths of the corridors to rooms j and j+1 on the next level, respectively. Corridor lengths do not exceed 10^9.

The sum of n over all tests does not exceed 1000.

For each test, print the expected path length on a separate line. The answer must have a relative or absolute error of at most 10^-6.