Несмотря на то что программный комитет работает достаточно слаженно, не обходится и без ожесточённых споров. Например, о том, какой клиент системы контроля версий удобнее в использовании: программа с графическим интерфейсом или консольная утилита.

Рассмотрим какую-либо команду консольной утилиты. Подстроку этой команды, которая не является подстрокой никакой другой команды утилиты, можно назвать ключевой, поскольку она однозначно идентифицирует команду. В последних версиях утилиты можно не вводить команду полностью, достаточно лишь ввести любую ключевую подстроку этой команды.

Сторонник консольной утилиты хочет убедить весь остальной программный комитет использовать именно её. Чтобы показать, насколько быстро и удобно с ней работать, он хочет найти для каждой команды ключевую подстроку минимальной длины. Помогите ему в этом.

В первой строке записано целое число n (2 ≤ n ≤ 1000) — количество команд консольной утилиты. В следующих n строках записаны эти команды — непустые строки, состоящие из строчных латинских букв. Длина каждой команды не превосходит 100. Никакая команда не является подстрокой другой команды.

Выведите n строк. В i-й строке должна быть записана любая из самых коротких ключевых подстрок i-й команды (команды занумерованы в том порядке, в котором они даны на входе).