Conspiracy
Petya and Vasya are playing a game of spies, where the main objective is to exchange secret messages while keeping them confidential. To achieve this, they use a special cipher.
The encryption and decryption process is straightforward: each letter α of the Russian alphabet is mapped to a specific sequence of Latin alphabet letters p_{α}. In the message, every occurrence of each letter α is replaced with its corresponding p_{α}. To further confuse any potential eavesdroppers, Petya and Vasya have agreed that only the lexicographically smallest word in the original message is important. Remember, a string a is considered lexicographically smaller than a string b if there exists an index i such that for all j < i, the equality a_j = b_j holds, and at the same time a_i < b_i, or if the string a is a prefix of the string b.
Recently, Petya proposed a new letter transformation table to Vasya:
Now, Vasya is struggling to decrypt Petya's messages quickly and has asked for your help. Your task is to determine the position of the word that, before encryption, was the lexicographically smallest in the Russian alphabet.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 1000), representing the number of words in the cipher. The following n lines each contain one word, composed of lowercase Latin letters, representing the text of the cipher Vasya received. Each word has a maximum length of 50.
Output
Output the position of the word in the cipher that, before encryption, was the lexicographically smallest in the Russian alphabet. The words in the cipher are numbered starting from one, in the order they appear in the input.