This page is still under construction.

Parts of this page are still being built. What you see may change.

Humble Numbers

Interview

Time limit1sMemory limit128 MB

Summary
For each n up to 5842, print the nth number whose only prime factors are 2, 3, 5, or 7, formatted with the correct English ordinal suffix.
Level

Medium5 of 10

Topics
Dynamic programming, Math, Implementation, Brute force
Solved
No attempts yet

Problem

A number whose only prime factors are 2, 3, 5, or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... lists the first 20 humble numbers.

Write a program that finds and prints the nnth element of this sequence.

Input

The input consists of one or more test cases. Each test case is a single integer nn (1≤n≤58421 \le n \le 5842). The input is terminated by a line containing 00, which is not processed.

Output

For each test case, print exactly one line in the following format:

The <n><suffix> humble number is <number>.

Here <number> is the nnth humble number, and <suffix> is the correct English ordinal suffix for nn ("st", "nd", "rd", or "th"). For example, 1 becomes "1st", 2 becomes "2nd", 3 becomes "3rd", while 11, 12, and 13 become "11th", "12th", and "13th".

Examples3

  1. Example 1

    Input
    1
2
3
4
11
12
13
21
22
23
100
1000
5842
0
    Expected output
    The 1st humble number is 1.
The 2nd humble number is 2.
The 3rd humble number is 3.
The 4th humble number is 4.
The 11th humble number is 12.
The 12th humble number is 14.
The 13th humble number is 15.
The 21st humble number is 28.
The 22nd humble number is 30.
The 23rd humble number is 32.
The 100th humble number is 450.
The 1000th humble number is 385875.
The 5842nd humble number is 2000000000.

  2. Example 2

    Input
    10
11
12
13
14
0
    Expected output
    The 10th humble number is 10.
The 11th humble number is 12.
The 12th humble number is 14.
The 13th humble number is 15.
The 14th humble number is 16.

  3. Example 3

    Input
    31
32
33
41
42
43
0
    Expected output
    The 31st humble number is 50.
The 32nd humble number is 54.
The 33rd humble number is 56.
The 41st humble number is 81.
The 42nd humble number is 84.
The 43rd humble number is 90.