Card Collection and Model Exchange

Sandy and Sue are both enthusiastic about collecting cards found in crispy noodles. However, their motivations differ: Sue collects cards for the pretty character illustrations while Sandy collects them to eventually redeem an awesome character model.

Each card is marked with a sequence of numbers. More specifically, the i-th card is represented by a sequence of length \(M_i\). To be eligible for an exchange, one must collect \(N\) cards. For these \(N\) cards, if each card contains a contiguous substring of length \(k\) such that all these substrings are similar, then one can redeem a level \(k\) character model.

Two substrings of the same length (say, \(a_1,a_2,\dots,a_k\) and \(b_1,b_2,\dots,b_k\)) are defined to be similar if there exists an integer \(d\) for which \(a_i + d = b_i\) for every \(1 \le i \le k\). In other words, the two substrings have the same pattern of differences between consecutive elements.

Sandy originally had too few cards, so Sue generously gave her some cards on her birthday. With Sue's help, Sandy finally collected \(N\) cards, but now he is unsure about the highest model level (i.e. the maximum \(k\)) he can redeem. Your task is to determine the maximum level \(k\) such that it is possible to select from each card a contiguous substring of length \(k\) whose difference sequence (i.e. \(a_2-a_1, a_3-a_2, \dots, a_k-a_{k-1}\)) is identical across all selected substrings.

Note: A single element (i.e. \(k = 1\)) is always considered valid since no differences exist to compare.

Hint: The problem essentially reduces to finding the longest common contiguous subarray among the "difference arrays" of all \(N\) cards. For a card with sequence \(A = a_1,a_2,\dots,a_M\), its difference array is defined as \(D = [a_2 - a_1, a_3 - a_2, \dots, a_M - a_{M-1}]\).

inputFormat

The first line of input contains a single integer \(N\) (the number of cards).

For each of the next \(N\) cards, the input is given on a separate line. Each such line starts with an integer \(M_i\) (the length of the \(i\)-th card's sequence), followed by \(M_i\) space-separated integers representing the numbers on the card.

It is guaranteed that \(M_i \ge 1\) for all \(i\) and that \(N \ge 1\).

outputFormat

Output a single integer representing the maximum possible level \(k\) (i.e. the maximum length of a common contiguous substring, chosen from each card, whose difference sequences are identical). Remember that if no common difference sequence exists, you can always choose \(k = 1\).

sample

3
3 1 2 3
3 2 3 4
3 3 4 5

3