Схожі імена
Якось n друзів зібралися пограти в "Among us", але вони хотіли, щоб кожен, хто заходить у лобі, розумів, що вони грають разом. Для цього вони вирішили вибрати нікнейми з подібним початком, але оскільки кожному дорогий його поточний нікнейм, ніхто не хоче його сильно змінювати.
Як компроміс було прийнято таке рішення: кожен гравець зрушить свій нікнейм по циклу на певну кількість символів так, щоб спільний префікс нікнеймів усіх гравців був якомога довшим. Циклічним зсувом рядка s = s[0]s[1]...s[n] називається рядок виду s[i] = s[i]s[i+1]..s[n]s[0]s[1]...s[i−1], а префіксом - рядок виду p[i] = s[0]s[1]...s[i].
Отже, повертаючись до нікнеймів: вирішити цю задачу належить вам, тому що гравці - не програмісти, і для них це занадто складно. Допоможіть їм знайти максимальний спільний префікс, який можна отримати, зсунувши їх нікнейми по циклу.
Вхідні дані
У першому рядку задано число n (1 ≤ n ≤ 10^5) - кількість гравців.
У наступних n рядках задано нікнейми гравців: у i-му рядку дано нікнейм i-го гравця s[i] (1 ≤ s[i] ≤ 10^5) - послідовність малих латинських літер. Гарантується, що сума довжин усіх нікнеймів не перевищує 10^5.
Вихідні дані
Знайдіть довжину найбільшого спільного префікса, який можуть отримати гравці, застосувавши до своїх нікнеймів якісь циклічні зсуви.