The Queen's English

Time limit1sMemory limit128 MB

Summary

Spell each integer below one billion in formal British English words with hyphens and ands.

Level: Easy3 of 10
Topics: Implementation, String
Solved: No attempts yet

Problem

In formal British written English, tens and units are joined with a hyphen, and the word "and" separates the hundreds from any tens or units that follow. The number 123 is written "one hundred and twenty-three".

Large numbers are split into triads, meaning groups of three digits, and each triad is followed by its own suffix. 123456 is written "one hundred and twenty-three thousand four hundred and fifty-six".

The last triad has one extra rule. If a large number ends in a triad that has a tens or units component but no hundreds component, that triad takes an "and" in front of it. So 1001001 is "one million one thousand and one".

Write a program that prints the correct British written form of a value of up to 9 digits, that is, below one short billion. Mind the spellings: "fifteen" and "fifty" take an f rather than a v, and "forty" has no u.

Input

Each line holds one integer $n$ ( $1 \le n < 10^9$ ), the value to spell out. A line holding 0 ends the input.

Output

Print one line per test, in the form Test k: words. Here k is the position of the test in the input counting from 1, and the words of the value are separated by single spaces.

Examples1

Example 1

Input

Expected output

Test 1: one hundred and twenty-three
Test 2: one million one thousand and one
Test 3: nine hundred million ninety thousand and nine