Ensure that you are logged in and have the required permissions to access the test.
HackerEarth City can be represented as an infinite number of houses standing next to each other and numerated starting with from left to right. Recently 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 non-empty sets of positive integers . The -th person can live in any house from the set . You have to choose a house for each person. More formally, you have to create an array such that for all , and denotes the house of the -th person.
Since all of them are close friends, they always attend their neighbor's birthdays. Let denote the distance between -th person and the closest neighbor to his left (some person such that and is maximum). If he doesn't have any such neighbor, we say that . Let equivalently denote the distance to the closest neighbor to his right.
You would like to create in such a way that is minimized.
Find and print the minimum possible value of .
Input
The first line of the input contains a single integer the number of testcases ().
Description of independent testcases follow. For each individual test, a single line contains one integer the number of sets ().
Next lines describe the sets. The -th line contains the description of in the following format: . Here, is the size of (, ).
It is guaranteed that every pair of sets has an empty intersection (for each , ). Also, it is guaranteed that and over all sets over all testcases does not exceed .
Output
The output should contain integers, each in a new line the minimum possible value of for each testcase.
In first testcase, you can create and achieve .
In second testcase, achieves .