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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Map;
import java.io.Writer;
import java.util.Map.Entry;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        CDeepDownBelow solver = new CDeepDownBelow();
        solver.solve(1, in, out);
        out.close();
    }

    static class CDeepDownBelow {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            var tc = in.nextInt();
            for (int i = 0; i < tc; i++) {
                solution(i, in, out);
            }
        }

        void solution(int testNumber, InputReader in, OutputWriter out) {
            int caves = in.nextInt();
            EzIntIntTreeMap ez = new EzIntIntTreeMap();
            for (int i = 0; i < caves; i++) {
                int mn = in.nextInt();
                int[] monsters = in.nextIntArray(mn);
                int powerRequired = 0;
                for (int j = 0; j < mn; j++) {
                    int a = monsters[j];
                    powerRequired = Math.max(powerRequired, a - j);
                }
                int curr = ez.get(powerRequired);
                ez.put(powerRequired, mn + curr);
            }

            // greedy, figure out smallest power level required per cave

            int requiredPower = 0;
            int gained = 0;
            for (int t : ez.keys()) {
                int z = ez.get(t);
                requiredPower = Math.max(requiredPower, t - gained);
                gained += z;
            }

            out.println(requiredPower + 1);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; ++i) array[i] = nextInt();
            return array;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static interface EzIntIntMapIterator {
        boolean hasNext();

        int getKey();

        int getValue();

        void next();

    }

    static class EzIntIntTreeMap implements EzIntIntSortedMap {
        private static final int DEFAULT_CAPACITY = 10;
        private static final double ENLARGE_SCALE = 2.0;
        private static final int HASHCODE_INITIAL_VALUE = 0x811c9dc5;
        private static final int HASHCODE_MULTIPLIER = 0x01000193;
        private static final boolean BLACK = false;
        private static final boolean RED = true;
        private static final int NULL = 0;
        private static final int DEFAULT_NULL_VALUE = (new int[1])[0];
        private int[] keys;
        private int[] values;
        private int[] left;
        private int[] right;
        private int[] p;
        private boolean[] color;
        private int size;
        private int root;
        private boolean returnedNull;

        public EzIntIntTreeMap() {
            this(DEFAULT_CAPACITY);
        }

        public EzIntIntTreeMap(int capacity) {
            if (capacity < 0) {
                throw new IllegalArgumentException("Capacity must be non-negative");
            }
            capacity++;
            keys = new int[capacity];
            values = new int[capacity];
            left = new int[capacity];
            right = new int[capacity];
            p = new int[capacity];
            color = new boolean[capacity];
            color[NULL] = BLACK;
            size = 0;
            root = NULL;
            returnedNull = false;
        }

        public EzIntIntTreeMap(EzIntIntMap map) {
            this(map.size());
            for (EzIntIntMapIterator it = map.iterator(); it.hasNext(); it.next()) {
                put(it.getKey(), it.getValue());
            }
        }

        public EzIntIntTreeMap(Map<Integer, Integer> javaMap) {
            this(javaMap.size());
            for (Map.Entry<Integer, Integer> e : javaMap.entrySet()) {
                put(e.getKey(), e.getValue());
            }
        }

        public int size() {
            return size;
        }

        public int get(int key) {
            int x = root;
            while (x != NULL) {
                if (key < keys[x]) {
                    x = left[x];
                } else if (key > keys[x]) {
                    x = right[x];
                } else {
                    returnedNull = false;
                    return values[x];
                }
            }
            returnedNull = true;
            return DEFAULT_NULL_VALUE;
        }

        public int put(int key, int value) {
            int y = NULL;
            int x = root;
            while (x != NULL) {
                //noinspection SuspiciousNameCombination
                y = x;
                if (key < keys[x]) {
                    x = left[x];
                } else if (key > keys[x]) {
                    x = right[x];
                } else {
                    final int oldValue = values[x];
                    values[x] = value;
                    returnedNull = false;
                    return oldValue;
                }
            }
            if (size == color.length - 1) {
                enlarge();
            }
            int z = ++size;
            keys[z] = key;
            values[z] = value;
            p[z] = y;
            if (y == NULL) {
                root = z;
            } else {
                if (key < keys[y]) {
                    left[y] = z;
                } else {
                    right[y] = z;
                }
            }
            left[z] = NULL;
            right[z] = NULL;
            color[z] = RED;
            fixAfterAdd(z);
            returnedNull = true;
            return DEFAULT_NULL_VALUE;
        }

        private int successorNode(int x) {
            if (right[x] != NULL) {
                x = right[x];
                while (left[x] != NULL) {
                    x = left[x];
                }
                return x;
            } else {
                int y = p[x];
                while (y != NULL && x == right[y]) {
                    //noinspection SuspiciousNameCombination
                    x = y;
                    y = p[y];
                }
                return y;
            }
        }

        private void fixAfterAdd(int z) {
            while (color[p[z]] == RED) {
                if (p[z] == left[p[p[z]]]) {
                    int y = right[p[p[z]]];
                    if (color[y] == RED) {
                        color[p[z]] = BLACK;
                        color[y] = BLACK;
                        color[p[p[z]]] = RED;
                        z = p[p[z]];
                    } else {
                        if (z == right[p[z]]) {
                            z = p[z];
                            rotateLeft(z);
                        }
                        color[p[z]] = BLACK;
                        color[p[p[z]]] = RED;
                        rotateRight(p[p[z]]);
                    }
                } else {
                    int y = left[p[p[z]]];
                    if (color[y] == RED) {
                        color[p[z]] = BLACK;
                        color[y] = BLACK;
                        color[p[p[z]]] = RED;
                        z = p[p[z]];
                    } else {
                        if (z == left[p[z]]) {
                            z = p[z];
                            rotateRight(z);
                        }
                        color[p[z]] = BLACK;
                        color[p[p[z]]] = RED;
                        rotateLeft(p[p[z]]);
                    }
                }
            }
            color[root] = BLACK;
        }

        private void rotateLeft(int x) {
            int y = right[x];
            right[x] = left[y];
            if (left[y] != NULL) {
                p[left[y]] = x;
            }
            p[y] = p[x];
            if (p[x] == NULL) {
                root = y;
            } else {
                if (x == left[p[x]]) {
                    left[p[x]] = y;
                } else {
                    right[p[x]] = y;
                }
            }
            left[y] = x;
            p[x] = y;
        }

        private void rotateRight(int x) {
            int y = left[x];
            left[x] = right[y];
            if (right[y] != NULL) {
                p[right[y]] = x;
            }
            p[y] = p[x];
            if (p[x] == NULL) {
                root = y;
            } else {
                if (x == right[p[x]]) {
                    right[p[x]] = y;
                } else {
                    left[p[x]] = y;
                }
            }
            right[y] = x;
            p[x] = y;
        }

        public int[] keys() {
            int[] result = new int[size];
            for (int i = 0, x = firstNode(); x != NULL; x = successorNode(x), i++) {
                result[i] = keys[x];
            }
            return result;
        }

        public EzIntIntMapIterator iterator() {
            return new EzIntIntTreeMapIterator();
        }

        private void enlarge() {
            int newLength = Math.max(color.length + 1, (int) (color.length * ENLARGE_SCALE));
            keys = Arrays.copyOf(keys, newLength);
            values = Arrays.copyOf(values, newLength);
            left = Arrays.copyOf(left, newLength);
            right = Arrays.copyOf(right, newLength);
            p = Arrays.copyOf(p, newLength);
            color = Arrays.copyOf(color, newLength);
        }

        private int firstNode() {
            int x = root;
            while (left[x] != NULL) {
                x = left[x];
            }
            return x;
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EzIntIntTreeMap that = (EzIntIntTreeMap) o;

            if (size != that.size) {
                return false;
            }
            for (int x = firstNode(), y = that.firstNode();
                 x != NULL;
                //noinspection SuspiciousNameCombination
                 x = successorNode(x), y = that.successorNode(y)
            ) {
                if (keys[x] != that.keys[y] || values[x] != that.values[y]) {
                    return false;
                }
            }
            return true;
        }

        public int hashCode() {
            int hash = HASHCODE_INITIAL_VALUE;
            for (int x = firstNode(); x != NULL; x = successorNode(x)) {
                hash = (hash ^ PrimitiveHashCalculator.getHash(keys[x])) * HASHCODE_MULTIPLIER;
                hash = (hash ^ PrimitiveHashCalculator.getHash(values[x])) * HASHCODE_MULTIPLIER;
            }
            return hash;
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append('{');
            for (int x = firstNode(); x != NULL; x = successorNode(x)) {
                if (sb.length() > 1) {
                    sb.append(", ");
                }
                sb.append(keys[x]);
                sb.append('=');
                sb.append(values[x]);
            }
            sb.append('}');
            return sb.toString();
        }

        private class EzIntIntTreeMapIterator implements EzIntIntMapIterator {
            private int x;

            private EzIntIntTreeMapIterator() {
                x = firstNode();
            }

            public boolean hasNext() {
                return x != NULL;
            }

            public int getKey() {
                if (x == NULL) {
                    throw new NoSuchElementException("Iterator doesn't have more entries");
                }
                return keys[x];
            }

            public int getValue() {
                if (x == NULL) {
                    throw new NoSuchElementException("Iterator doesn't have more entries");
                }
                return values[x];
            }

            public void next() {
                if (x == NULL) {
                    return;
                }
                x = successorNode(x);
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(int i) {
            writer.println(i);
        }

    }

    static interface EzIntIntSortedMap extends EzIntIntMap {
        int size();

        EzIntIntMapIterator iterator();

        boolean equals(Object object);

        int hashCode();

        String toString();

    }

    static interface EzIntIntMap {
        int size();

        EzIntIntMapIterator iterator();

        boolean equals(Object object);

        int hashCode();

        String toString();

    }

    static final class PrimitiveHashCalculator {
        private PrimitiveHashCalculator() {
        }

        public static int getHash(int x) {
            return x;
        }

    }
}

