Петя та Вася грають у шпигунів. Головна мета цієї гри - обмінюватись секретними повідомленнями, зберігаючи конспірацію. Для этого Петя и Вася используют особый шифр. Метод шифрування та дешифрування дуже простий: кожній літері \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 У вихідний файл виведіть номер слова шифровки, яке до шифрування було лексикографічно мінімальним у російському алфавіті. Шифровки нумеруютюся з одиниці у порядку появи у вхідному файлі.