Конспирация
Петя и Вася играют в шпионов. Главная цель этой игры - обмениваться секретными сообщениями, сохраняя конспирацию. Для этого Петя и Вася используют особый шифр.
Метод шифровки и дешифровки очень прост: каждой букве α русского алфавита сопоставляется некоторая последовательность букв латинского алфавита p_{α}. Затем в сообщении все вхождения каждой буквы α заменяются на соответствующее ей p_{α}. А чтобы совсем запутать вероятного противника, Петя и Вася договорились, что значимым в исходном сообщении должно быть только лексикографически минимальное слово. Напомним, что строка a лексикографически меньше строки b, если существует такое i, что для любого j < i выполняется равенство a_j = b_j и при этом a_i < b_i, или строка a является префиксом строки b.
Недавно Петя предложил Васе использовать следующую таблицу преобразования букв:
Однако теперь Вася не успевает дешифровывать сообщения Пети вовремя и просит вас помочь ему - определить номер слова, которое до шифрования, записанное русскими буквами, было лексикографически минимальным.
Входные данные
Первая строка входного файла содержит одно целое число n (1 ≤ n ≤ 1000) - количество слов в шифровке. Следующие n строк содержат по одному слову, состоящему из маленьких латинских букв - текст шифровки, которую получил Вася. Длина слова не превышает 50.
Выходные данные
В выходной файл выведите номер слова шифровки, которое до шифрования было лексикографически минимальным в русском алфавите. Шифровки нумеруются с единицы в порядке появления во входном файле.