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