29409번 - Конспирация 다국어

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

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

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

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

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

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

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