Lily wants to go traveling. She has chosen n different cities. She plans to travel from the first city, the second city, the third city,…, to the n city in sequence, then from the first n city, the N-1 city and the N-2 city,… until the first city.

And the roads between the two cities are varied. Each road has a different length.

Lili don't want to go any road more than once, and she also want to make the shortest journey.

Data ensure that there are at least two roads between adjacent cities.

Please output the shortest total travel length.

The first line contains a T which means the number of data sets.

In each data set:

The first line contains one integers n — the number of cities in Lily’s plan.

The next i th line firstly contains one integer ki which is the number of road between i th city and i+1 th city ,and then ki distinct integers a1, a2, ..., aki — the distance of the road ai.

T <= 100       n ,ki <= 1000      1 <= ai <= 10000

for each data set, output answer in one line.