Similar names
Once upon a time, n friends were going to play "Among Us", but they also wanted the person who entered the lobby to be convinced that they entered together each time. To do this, they decided to choose nicknames with a similar beginning, but since it has become valuable to use his nickname, no one wants to change it much.
As a compromise, the following decision was made: each player will shift his nickname around the cycle by a certain number of characters so that the common prefix of nicknames of all players is as long as possible. A circular shift of a string s = s[0]s[1]..s[n] is a string of the form s[i] = s[i]s[i+1]..s [n]s[0]s[1]...s[i−1], and prefix is a string like p[i] = s[0]s[1]..s[i] .
So, returning to nicknames: you have to solve this problem, because the players are not programmers, and it is too difficult for them. Help them find the maximum common prefix they can get by looping through their nicknames.
Input
The first line contains the number n (1 ≤ n ≤ 10^5) - the number of players.
The following n lines contain the players' nicknames: the i-th line contains the nickname of the i-th player s[i] (1 ≤ s[i] ≤ 10^5) - a sequence of lowercase Latin letters. It is guaranteed that the sum of lengths of all nicknames does not exceed 10^5.
Output
Find the length of the largest common prefix that players can get by applying some kind of cyclic shifts to their nicknames.