Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Phone Code

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarpus has *n* friends in Tarasov city. Polycarpus knows phone numbers of all his friends: they are strings *s*_{1}, *s*_{2}, ..., *s*_{n}. All these strings consist only of digits and have the same length.

Once Polycarpus needed to figure out Tarasov city phone code. He assumed that the phone code of the city is the longest common prefix of all phone numbers of his friends. In other words, it is the longest string *c* which is a prefix (the beginning) of each *s*_{i} for all *i* (1 ≤ *i* ≤ *n*). Help Polycarpus determine the length of the city phone code.

Input

The first line of the input contains an integer *n* (2 ≤ *n* ≤ 3·10^{4}) — the number of Polycarpus's friends. The following *n* lines contain strings *s*_{1}, *s*_{2}, ..., *s*_{n} — the phone numbers of Polycarpus's friends. It is guaranteed that all strings consist only of digits and have the same length from 1 to 20, inclusive. It is also guaranteed that all strings are different.

Output

Print the number of digits in the city phone code.

Examples

Input

4

00209

00219

00999

00909

Output

2

Input

2

1

2

Output

0

Input

3

77012345678999999999

77012345678901234567

77012345678998765432

Output

12

Note

A prefix of string *t* is a string that is obtained by deleting zero or more digits from the end of string *t*. For example, string "00209" has 6 prefixes: "" (an empty prefix), "0", "00", "002", "0020", "00209".

In the first sample the city phone code is string "00".

In the second sample the city phone code is an empty string.

In the third sample the city phone code is string "770123456789".

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2018 07:16:43 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|