Конспірація#2776

Конспірація

1 секунда

64 мегабайти

Середня

Олег та Ігор грають у шпигунів. Головна мета гри — обмінюватися таємними повідомленнями, зберігаючи секретність. Для цього Олег та Ігор використовують спеціальний шифр.

Метод шифрування і дешифрування дуже простий: кожну літеру $α$ кириличної абетки замінюють певною послідовністю латинських літер $p_{α}$ p_\alpha. Далі, у повідомленні всі входження кожної $α$ замінюються на відповідне $p_{α}$ p_\alpha. Щоб ще більше збити з пантелику потенційного супротивника, Олег і Ігор домовилися, що значення має лише лексикографічно мінімальне слово в оригінальному повідомленні. Нагадаємо, що рядок $a$ лексикографічно менший за рядок $b$ , якщо існує $i$ , таке що для всіх $j < i$ j < i виконується рівність $a_{j} = b_{j}$ a_j = b_j і $a_{i} < b_{i}$ a_i < b_i, або якщо рядок $a$ є префіксом рядка $b$ .

Нещодавно Олег запропонував Ігору використати таку таблицю перетворення літер:

Тепер Ігор не може розшифровувати повідомлення Олега вчасно й просить вас йому допомогти: визначте номер слова, яке до шифрування (написане кирилицею) було лексикографічно мінімальним.

Вхідні дані

У першому рядку міститься одне ціле число $n$ ( $1 \leq n \leq 1000$ 1 \leq n \leq 1000) — кількість зашифрованих слів. Далі в наступних $n$ рядках записано по одному слову, що складається з малих латинських літер — текст шифру, отриманого Ігорем. Довжина кожного слова не перевищує $50$ .

Вихідні дані

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

Приклади

Приклад 1