Longest Common Prefix

You are given a list of strings and your task is to find the longest common prefix among them. If there is no common prefix, output an empty string.

The problem requires you to consider multiple test cases, where the first line contains the integer n - the number of strings, followed by n lines each containing one string. Your solution should output the longest common prefix shared by all the input strings.

For example, given the strings "flower", "flow", and "flight", the longest common prefix is "fl". If no common prefix exists (for example, in the strings "dog", "racecar", and "car"), your program should output an empty string.

Note: When writing your solution, please ensure it reads input from stdin and writes the result to stdout. All formulas or conditions (if any) should be formatted in LaTeX, for instance, you may express the concept of prefix as: \(\text{prefix}(s)\).

inputFormat

The input will be read from stdin and has the following format:

n
s_{1}
...
s_{n}

Where:

• n is the number of strings.
• Each of the following n lines contains a string si.

outputFormat

Output a single line containing the longest common prefix string among the given strings. If there is no common prefix, output an empty string.

## sample

3
flower
flow
flight

fl