Student Numbers

Interview

Time limit2sMemory limit128 MB

Summary

Given N equal-length numeric strings, find the smallest suffix length k so that all suffixes of length k remain distinct.

Level: Easy3 of 10
Topics: String, Brute force, Hash map
Solved: No attempts yet

Problem

To manage students efficiently, each student is assigned a unique student number. A student number is a string made only of digits from 0 to 9. All student numbers are different, and they all have the same length.

After assigning the numbers, assistant Jinyoung Kim wonders whether the numbers are longer than necessary. Suppose the following 7-digit student numbers are given.

Name	Number
Oh Minsik	1212345
Kim Hyungtaek	1212356
Lee Dongho	0033445

In this case, the full 7 digits are not needed. If only the last three digits are kept, all student numbers are still distinguishable.

Name	Number
Oh Minsik	345
Kim Hyungtaek	356
Lee Dongho	445

However, keeping fewer than three digits from the end cannot make all student numbers distinct.

Given the student numbers, find the smallest k such that keeping only the last k digits of each number still makes all student numbers distinct.

Input

The first line contains the number of students N. (2 <= N <= 1,000)

Each of the next N lines contains one student number. All student numbers are different, have the same length, and consist only of digits from 0 to 9. The length of each student number is at most 100.

Output

Print the smallest k such that keeping only the last k digits makes all student numbers distinct.

Examples1

Example 1
Input
```
3
1212345
1212356
0033445
```
Expected output
```
3
```