Try our new interface for solving problems



Time limit 1 second
Memory limit 64 MiB

In the language of the trolls have 5 consonants: {h, k, m, r, t}, and 3 vowels: {a, o, u}. Each word begins with a consonant letters, with the word can not be two consecutive vowels or consonants.

N trolls in turn called the shortest word that has not called any of the previous trolls. If several options, the troll vibiraem smallest lexicographically. Lexicographic order h < k < m < r < t < a < o < u. In this case, the word is compared first by the first letter. If the first letter of the same, for the second, etc.

Find the word that will call N-th troll.

Input data

The first line contains a single number 1T100, the number of test cases. Each and subsequent T lines contains one integer 1N1000000000(1e9) – the number of Troll.

Output data

For each number N of input data, output in a single line answer to the problem in accordance with the format specified in the example.


Input example #1
Output example #1
Case #1: ha
Case #2: tut
Case #3: muhomor
Source The 2012 All-Ukrainian Collegiate Programming Contest Round I Training Contest 19 April 2012