Integer to English Words

Math
String
Recursion

Given a whole number num, return how it is written out in English words, following the rules below exactly.

The words you may use, each starting with a capital letter:

Zero
One Two Three Four Five Six Seven Eight Nine
Ten Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen
Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety
Hundred Thousand Million Billion

How to build the answer:

Split the digits into groups of three, starting from the right. From left to right the groups count billions, millions, thousands and ones.
Write each group that isn't zero as a number from 1 to 999, then its scale word: Billion, Million or Thousand (the ones group has none). A group that is all zeros is left out completely, scale word and all.
A number from 1 to 999: if its hundreds digit isn't zero, write that digit's word and then Hundred. Then the last two digits: from 1 to 19 they are a single word; from 20 to 99 they are a tens word, followed by the ones digit's word if that digit isn't zero. When the last two digits are 00, write nothing for them.
Separate the words with exactly one space, with no space at the start or end. There is no "and", no hyphen and no comma.

0 is the only number written as Zero.

Examples

Example 1

Input

405

Output

␣

Explain:

The hundreds digit gives Four Hundred. The last two digits are 05, which is just Five.

Example 2

Input

7013

Output

␣

Explain:

The groups are 7 and 013. 7 thousand, then 13 is one word of its own.

Example 3

Input

2000050019

Output

␣

Explain:

The groups are 2, 000, 050 and 019. The millions group is zero, so it doesn't appear at all.

Constraints

0 <= num <= 2³¹ - 1 (that is, 2147483647)

Stuck? Hint 1

Every group of three digits is said the same way; only the scale word after it changes. Solve 1 to 999 once and reuse it.

Input

Expected Output

␣

Ctrl / ⌘ + Enter

Integer to English Words

Math
String
Recursion

Given a whole number num, return how it is written out in English words, following the rules below exactly.

The words you may use, each starting with a capital letter:

Zero
One Two Three Four Five Six Seven Eight Nine
Ten Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen
Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety
Hundred Thousand Million Billion

How to build the answer:

Split the digits into groups of three, starting from the right. From left to right the groups count billions, millions, thousands and ones.
Write each group that isn't zero as a number from 1 to 999, then its scale word: Billion, Million or Thousand (the ones group has none). A group that is all zeros is left out completely, scale word and all.
A number from 1 to 999: if its hundreds digit isn't zero, write that digit's word and then Hundred. Then the last two digits: from 1 to 19 they are a single word; from 20 to 99 they are a tens word, followed by the ones digit's word if that digit isn't zero. When the last two digits are 00, write nothing for them.
Separate the words with exactly one space, with no space at the start or end. There is no "and", no hyphen and no comma.

0 is the only number written as Zero.

Examples

Example 1

Input

405

Output

␣

Explain:

The hundreds digit gives Four Hundred. The last two digits are 05, which is just Five.

Example 2

Input

7013

Output

␣

Explain:

The groups are 7 and 013. 7 thousand, then 13 is one word of its own.

Example 3

Input

2000050019

Output

␣

Explain:

The groups are 2, 000, 050 and 019. The millions group is zero, so it doesn't appear at all.

Constraints

0 <= num <= 2³¹ - 1 (that is, 2147483647)

Stuck? Hint 1

Every group of three digits is said the same way; only the scale word after it changes. Solve 1 to 999 once and reuse it.

Input

Expected Output

␣

Ctrl / ⌘ + Enter