In a certain video game, the player controls a hero characterized by a single integer value: power. The hero will have to beat monsters that are also characterized by a single integer value: armor.

On the current level, the hero is facing n caves. To pass the level, the hero must enter all the caves in some order, each cave exactly once, and exit every cave safe and sound. When the hero enters cave i, he will have to fight k_i monsters in a row: first a monster with armor a_{i, 1}, then a monster with armor a_{i, 2} and so on, finally, a monster with armor a_{i, k_i}.

The hero can beat a monster if and only if the hero's power is strictly greater than the monster's armor. If the hero can't beat the monster he's fighting, the game ends and the player loses. Note that once the hero enters a cave, he can't exit it before he fights all the monsters in it, strictly in the given order.

Each time the hero beats a monster, the hero's power increases by 1.

Find the smallest possible power the hero must start the level with to be able to enter all the caves in some order and beat all the monsters.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^5). Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^5) — the number of caves.

The i-th of the next n lines contains an integer k_i (1 ≤ k_i ≤ 10^5) — the number of monsters in the i-th cave, followed by k_i integers a_{i, 1}, a_{i, 2}, …, a_{i, k_i} (1 ≤ a_{i, j} ≤ 10^9) — armor levels of the monsters in cave i in order the hero has to fight them.

It is guaranteed that the sum of k_i over all test cases does not exceed 10^5.

Output

For each test case print a single integer — the smallest possible power the hero must start the level with to be able to enter all the caves in some order and beat all the monsters.

Example

Input


2
1
1 42
2
3 10 15 8
2 12 11


Output


43
13

Note

In the first test case, the hero has to beat a single monster with armor 42, it's enough to have power 43 to achieve that.

In the second test case, the hero can pass the level with initial power 13 as follows: 

  * enter cave 2: 
    * beat a monster with armor 12, power increases to 14; 
    * beat a monster with armor 11, power increases to 15; 
  * enter cave 1: 
    * beat a monster with armor 10, power increases to 16; 
    * beat a monster with armor 15, power increases to 17; 
    * beat a monster with armor 8, power increases to 18. 
import java.util.*;
import java.io.*;
public class Test {
	public static void main(String[] args) throws IOException {
	   Scanner sc = new Scanner(System.in);
	   PrintWriter pw = new PrintWriter(System.out);
	   int  t = sc.nextInt();
	   while(t-->0) {
		
		int k = sc.nextInt();
		ArrayList <Long> [] arr = new ArrayList [k];
		for (int i = 0;i<k;i++) {
			arr[i] = new ArrayList<Long>();
			int size = sc.nextInt();
			while (size -->0) {
				arr[i].add(sc.nextLong());
			}
		}
		Pair max [] = new Pair [k];
		int count = 0;
		for (ArrayList<Long> cave : arr) {
			long caveMax = Long.MIN_VALUE;
			for (int i = 0;i<cave.size();i++) {
				caveMax = Math.max(caveMax,cave.get(i)-i);
			}
			max[count] = new Pair(caveMax,cave.size());
			count++;
		}
		
		Arrays.sort(max);
		long cumu = 0;
		for (int i = 0;i<k;i++) {
			max[i].x-=cumu;
			cumu += max[i].y;
		}
		long ans = 0;
		for(int i = 0;i<k;i++) {
			ans = Math.max(ans, max[i].x);
		}
		System.out.println(ans+1);
		
		
	}}
	public static double solve(int currTrial, int lampsMask) {
		if(lampsMask ==0 || currTrial==101) {
			return (currTrial-1);
		}
		if(dp[currTrial][lampsMask]!=-1) {
			return dp[currTrial][lampsMask];
		}
		double tot = 0;
		for(int i = 0;i<m;i++) {
			tot += (solve(currTrial+1,lampsMask^switchMask[i])/m);
		}
	    
		return dp[currTrial][lampsMask] = (tot);
		
	}
	static double [][] dp ;
	static double probFactor;
	static int m;
	static int [] switchMask;
    static int lcs(char[] X, char[] Y, int m, int n)
     {
         if (m == 0 || n == 0)
             return 0;
         if (X[m - 1] == Y[n - 1])
             return 1 + lcs(X, Y, m - 1, n - 1);
         else
             return Math.max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
     }
	    public static void dfs1(int node) {
	    	visited1[node] = true;
	    	for(int v :adjLists1[node]) {
	    		if(!visited1[v]) {
	    			dfs1(v);
	    		}
	    	}
	    	
	    }
	   static int maxSubsequenceSubstring(char[] X,char[] Y,int n,int m)
	    {
	        // Base Case
	        if (n==0 || m==0) return 0;
	        
	        // Calls on smaller inputs
	        
	        // if the last char of both strings are equal
	        if(X[n-1] == Y[m-1])
	        {
	            return  1 + maxSubsequenceSubstring(X,Y,n-1,m-1);
	        }
	        
	        // if the last char of both strings are not equal
	        else
	        {
	            return maxSubsequenceSubstring(X,Y,n-1,m);    
	        }
	    }
	    public static void dfs2(int node) {
	    	visited2[node] = true;
	    	for(int v :adjLists2[node]) {
	    		if(!visited2[v]) {
	    			dfs2(v);
	    		}
	    	}
	    }
	    static class Picture implements Comparable{
	    	char [][] pixels;
	    	int numOFOnes;
	    	int idx;
	    	public Picture(char [][] pixels, int numOfOnes, int idx) {
	    		this.pixels = pixels;
	    		this.numOFOnes = numOfOnes;
	    		this.idx = idx;
	    	}
			@Override
			public int compareTo(Object arg0) {
				Picture p = (Picture) arg0;
				return numOFOnes - p.numOFOnes;
			}
	    	
	    }
	    static  ArrayList<Integer> [] adjLists1;
	    static ArrayList<Integer> [] adjLists2;
	    static boolean []visited1;
	    static boolean [] visited2;
		static int [] arr ;
		static int d [] ;
		
	   static  HashSet<Long> hs = new HashSet<Long>();
	  
	public static int idxOf(String s,char c) {
		int idx = -2;
		for(int i = 0;i<s.length();i++) {
			if(s.charAt(i)==c) {
				return i;
			}
		}
		return idx;
	}
	static ArrayList<Long >start;
	static ArrayList<Long> end;
	public static void dfs (int idx) {
		can[idx] = true;
		for(int i = 0;i<start.size();i++) {
			if((start.get(i)<start.get(idx)&& end.get(i)>start.get(idx)||(start.get(i)<end.get(idx)&& end.get(i)>end.get(idx)))){
				if(!can[i]) {
				dfs(i);
			}}
		}
	}
	static boolean [] can ; 
	static int n;
	
	static int [] [] sol;
	static int [] g;
	public static void constructSol() {
		for(int i = 1;i<sol.length;i++) {
			for(int j = 1;j<10;j++) {
				if(g[i] == j) {
					sol[i][j] = sol[i-1][j]+1;
				}
				else {
					sol[i][j] = sol[i-1][j];
				}
			}
		}
	}
	public static void prod() {
		for(int i=1;i<g.length;i++) {
			int n = i;
		if(n<10) {
			g[ n] = n;
		    continue;
		}
		int prod = 1;
		while(n>0) {
			if(n%10!=0) {
				prod*= (n%10);
				
			}
			n/=10;
		}
		//System.out.println(prod);
		g[i] = g[prod];
	
	}}
	public static  boolean isPalindrome(String s) {
		
		for(int i = 0;i<=s.length()/2;i++) {
			if(s.charAt(i)!=s.charAt(s.length()-1-i)) {
				return false;
			}
		}
		return true;
	}
	public static long logBase2(long n) {
		long ans = 0;
		while(n>1) {
			ans ++;
			n/=2;
		}
		return ans;
	}
	public static double getmostLeft(ArrayList<Circle> list) {
	        double min = Double.MAX_VALUE;
	        for (Circle c: list) {
	            min = Math.min(min, c.x - c.r);
	        }
	        return min;
	    }
 
	   public static double getmostRight(ArrayList<Circle> list) {
	        double max = Double.MIN_VALUE;
	        for (Circle c: list) {
	            max = Math.max(max, c.x + c.r);
	        }
	        return max;
	    }
	static class Circle{
		double x ;
		double y ;
		double r;
		int id;
		public Circle(double x, double y, double r) {
			this.x = x;
			this.y = y;
			this.r = r;
			
		}
		public String toString () {
			return x +" "+y+" "+r;
		}
		public boolean intersect(Circle o) {
			double dist = Math.sqrt((y-o.y)*(y-o.y)+(x-o.x)*(x-o.x));
			if(dist<=r+o.r) {
				return true;
			}
			return false;
		}
		public  Circle combine( Circle o) {
			double dist = Math.sqrt((y-o.y)*(y-o.y)+(x-o.x)*(x-o.x));
		    if(Math.abs(r-o.r)>=dist) {
		    	if(r>=o.r) {
		    		return this;
		    	}
		    	else {
		    		return o;
		    	}
		    }
 
			double cx = (x+o.x)/2.0;
			double cy = (y+o.y)/2.0;
			double rad = (dist +r +this.r)/2.0;
			return new Circle (cx, cy, rad);
		}
	}
	static class Pair implements Comparable {
		long x;
		int y;
		public Pair (long x, int y) {
			this.x = x;
			this.y = y;
			
		}
		@Override
		public int compareTo(Object arg0) {
			Pair p = (Pair) arg0;
		return Long.compare(x, p.x);
		}
	}
	public static String solve (String s) {
		Stack <String> st = new Stack<String>();
		for(int i = 0;i<s.length();i++) {
			if(s.charAt(i)==']') {
				String toEncode = "";
				while(!st.isEmpty()&&!st.peek().equals("[")) {
					toEncode = st.pop()+ toEncode;
				}
				st.pop();
				String toPush = "";
				int freq = Integer.parseInt(st.pop());
				while(freq-->0) {
					toPush+=toEncode;
				}
				st.push(toPush);
			}
			else {
				st.push(s.charAt(i)+"");
			}
			
		}
		String res = "";
		while(!st.isEmpty()) {
			res = st.pop() +res;
		}
		return res;
	}
	static String alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

	static String s;
	static ArrayList <Integer> prime;
	 static void simpleSieve(int limit)
	    {   
	        // Create a boolean array "mark[0..n-1]" and initialize
	        // all entries of it as true. A value in mark[p] will
	        // finally be false if 'p' is Not a prime, else true.
	        boolean mark[] = new boolean[limit+1];
	         
	        for (int i = 0; i < mark.length; i++)
	            mark[i] = true;
	      
	        for (int p=2; p*p<limit; p++)
	        {
	            // If p is not changed, then it is a prime
	            if (mark[p] == true)
	            {
	                // Update all multiples of p
	                for (int i=p*p; i<limit; i+=p)
	                    mark[i] = false;
	            }
	        }
	      
	        // Print all prime numbers and store them in prime
	        for (int p=2; p<limit; p++)
	        {
	            if (mark[p] == true)
	            {
	                prime.add(p);
	               // System.out.print(p + "  ");
	            }
	        }
	    }
 
	 
	 public static long gcd (long a, long b ) {
		 if(b==0) {
			 return a;
		 }
		 else {
			 return gcd (b, a%b);
		 }
	 }
	 
 static class Scanner {
 		StringTokenizer st;
 		BufferedReader br;
  
 		public Scanner(InputStream s) {
 			br = new BufferedReader(new InputStreamReader(s));
 		}
        public Scanner(FileReader r) {
        	br = new BufferedReader(r);
        }
 		public boolean hasNext() {
 			// TODO Auto-generated method stub
 			return false;
 		}
  
 		public String next() throws IOException {
 			while (st == null || !st.hasMoreTokens())
 				st = new StringTokenizer(br.readLine());
 			return st.nextToken();
 		}
  
 		public int nextInt() throws IOException {
 			return Integer.parseInt(next());
 		}
  
 		public long nextLong() throws IOException {
 			return Long.parseLong(next());
 		}
  
 		public String nextLine() throws IOException {
 			return br.readLine();
 		}
  
 		public double nextDouble() throws IOException {
 			String x = next();
 			StringBuilder sb = new StringBuilder("0");
 			double res = 0, f = 1;
 			boolean dec = false, neg = false;
 			int start = 0;
 			if (x.charAt(0) == '-') {
 				neg = true;
 				start++;
 			}
 			for (int i = start; i < x.length(); i++)
 				if (x.charAt(i) == '.') {
 					res = Long.parseLong(sb.toString());
 					sb = new StringBuilder("0");
 					dec = true;
 				} else {
 					sb.append(x.charAt(i));
 					if (dec)
 						f *= 10;
 				}
 			res += Long.parseLong(sb.toString()) / f;
 			return res * (neg ? -1 : 1);
 		}
  
 		public boolean ready() throws IOException {
 			return br.ready();
 		}
  
 	}
}