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