Рабочее место участника

Петя и Вася играют в шпионов. Главная цель этой игры – обмениваться секретными сообщениями, сохраняя конспирацию. Для этого Петя и Вася используют особый шифр.

Метод шифровки и дешифровки очень прост: каждой букве `alpha` русского алфавита сопоставляется некоторая последовательность букв латинского алфавита `p_alpha`. Затем в сообщении все вхождения каждой буквы `alpha` заменяются на соответствующее ей `p_alpha`. А чтобы совсем запутать вероятного противника, Петя и Вася договорились, что значимым в исходном сообщении должно быть только лексикографически минимальное слово. Напомним, что строка `a` лексикографически меньше строки `b`, если существует такое `i`, что для любого `j\ <\ i` выполняется равенство `a_j\ =\ b_j` и при этом `a_i\ <\ b_i`, или строка `a` является префиксом строки `b`.

Недавно Петя предложил Васе использовать следующую таблицу преобразования букв:

Однако теперь Вася не успевает дешифровывать сообщения Пети вовремя и просит вас помочь ему – определить номер слова, которое до шифрования, записанное русскими буквами, было лексикографически минимальным.

Первая строка входного файла содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 1000`) – количество слов в шифровке. Следующие `n` строк содержат по одному слову, состоящему из маленьких латинских букв – текст шифровки, которую получил Вася. Длина слова не превышает `50`.

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

6
yolka
jeti
yabloko
segodnya
schtab
kaktus

1

Пояснение к примеру: исходное сообщение состояло из слов ёлка, йети, яблоко, сегодня, штаб, кактус.