1. 

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #443 (Humble Numbers)
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=384
*
* @author Fabian Seidl
* @author Marcel Sachse
* @version 1.0, 03/25/2009
*
* Status : Accepted
* Runtime: 0.600
*/



import java.io.*;
import java.util.Scanner;

public class Main
{
private static final int MAX_INPUT = 5842;

public static void main(String[] args) throws IOException
{
BufferedInputStream bInput = new BufferedInputStream(System.in);
Scanner scanner = new Scanner(bInput);

Writer out = new BufferedWriter(new PrintWriter(System.out));

// Cache Variablen
long[] humble = new long[MAX_INPUT];
int index=0;
int searchstart = 0;
humble[0]=1;

int input;
while((input=scanner.nextInt())!=0)
{
int end = input-1;

while(index<end)
{
// n¦chste zahl suchen

long last = humble[index];
long next = Integer.MAX_VALUE;

for(int i=searchstart;i<=index;i++)
{
long n;

// suche kleinstm¨gliche komb. aus bish. zahlen * 2,3,5

n = humble[i]*2L;
if(n<next && n>last) next = n;

n = humble[i]*3L;
if(n<next && n>last) next = n;

n = humble[i]*5L;
if(n<next && n>last) next = n;


n = humble[i]*7L;
if(n<next && n>last)
{
next = n;

// nachdem ugly[i] * 7 verwendet wurde m¾ssen
// alle davor nicht weiter beachtet werden
searchstart = i;
}

}

// gefundene Zahl speichern
index++;
humble[index] = next;
}

// richtigen Suffix finden
String suf;


if((input % 100)/10==1)
{
suf="th";
}
else
switch ( input % 10 )
{
case 1: suf = "st"; break;
case 2: suf = "nd"; break;
case 3: suf = "rd"; break;
default: suf = "th";
}

out.append("The "+input+suf+" humble number is "+humble[end]+".\n");
}

out.flush();
out.close();
}

}