HackerEarth City can be represented as an infinite number of houses standing next to each other and numerated starting with 1 from left to right. Recently n people have decided to move in HackerEarth City. They haven't decided which houses to accommodate yet, so they kindly asked for your help.
You have n non-empty sets of positive integers S1,S2,…,Sn. The i-th person can live in any house from the set Si. You have to choose a house for each person. More formally, you have to create an array A1,A2,…,An such that for all i, Ai∈Si and Ai denotes the house of the i-th person.
Since all of them are close friends, they always attend their neighbor's birthdays. Let Bi denote the distance between i-th person and the closest neighbor to his left (some person j≠i such that Aj<Ai and Aj is maximum). If he doesn't have any such neighbor, we say that Bi=0. Let Ci equivalently denote the distance to the closest neighbor to his right.
You would like to create A1,A2,…,An in such a way that ∑B+∑C is minimized.
Find and print the minimum possible value of ∑B+∑C.
Input
The first line of the input contains a single integer t − the number of testcases (1≤t≤100).
Description of t independent testcases follow. For each individual test, a single line contains one integer n − the number of sets (2≤n≤105).
Next n lines describe the sets. The i-th line contains the description of Si in the following format: k,Si,1,Si,2,…,Si,k. Here, k is the size of Si (1≤k≤105, 1≤Si,1<Si,2<⋯<Si,k≤109).
It is guaranteed that every pair of sets has an empty intersection (for each 1≤i<j≤n, Si∩Sj=∅). Also, it is guaranteed that ∑n and ∑k over all sets over all testcases does not exceed 105.
Output
The output should contain t integers, each in a new line − the minimum possible value of ∑B+∑C for each testcase.
In first testcase, you can create A=[3,4,5] and achieve ∑B+∑C=0+1+1+1+1+0=4.
In second testcase, A=[9,8] achieves 1+0+0+1=2.
