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 \(S_1, S_2, \dots, S_n\). The \(i\)-th person can live in any house from the set \(S_i\). You have to choose a house for each person. More formally, you have to create an array \(A_1, A_2, \dots, A_n\) such that for all \(i\), \(A_i \in S_i\) and \(A_i\) denotes the house of the \(i\)-th person.
Since all of them are close friends, they always attend their neighbor's birthdays. Let \(B_i\) denote the distance between \(i\)-th person and the closest neighbor to his left (some person \(j \ne i\) such that \(A_j < A_i\) and \(A_j\) is maximum). If he doesn't have any such neighbor, we say that \(B_i = 0\). Let \(C_i\) equivalently denote the distance to the closest neighbor to his right.
You would like to create \(A_1, A_2, \dots, A_n\) in such a way that \(\sum{B} + \sum{C}\) is minimized.
Find and print the minimum possible value of \(\sum{B} + \sum{C}\).
Input
The first line of the input contains a single integer \(t\) \(-\) the number of testcases (\(1 \le t \le 100\)).
Description of \(t\) independent testcases follow. For each individual test, a single line contains one integer \(n\) \(-\) the number of sets (\(2 \le n \le 10^5\)).
Next \(n\) lines describe the sets. The \(i\)-th line contains the description of \(S_i\) in the following format: \(k, S_{i,1}, S_{i,2}, \dots, S_{i,k}\). Here, \(k\) is the size of \(S_i\) (\(1 \le k \le 10^5\), \(1 \le S_{i,1} < S_{i,2} < \dots < S_{i,k} \le 10^9\)).
It is guaranteed that every pair of sets has an empty intersection (for each \(1 \le i < j \le n\), \(S_i \cap S_j = \emptyset\)). Also, it is guaranteed that \(\sum{n}\) and \(\sum{k}\) over all sets over all testcases does not exceed \(10^5\).
Output
The output should contain \(t\) integers, each in a new line \(-\) the minimum possible value of \(\sum{B} + \sum{C}\) for each testcase.