Aronson#1809

Aronson

1 second

64 megabytes

Very easy

Aronson's sequence $a_{k}$ a_k is a sequence of integers defined by the sentence "t is the first, fourth, eleventh, ... letter of this sentence.", where the ... are filled in appropriately so that the sentence makes sense. The first few values are $1, 4, 11, 16, 24, 29, 33, 35, 39, ...$ \textbf{1}, \textbf{4}, \textbf{11}, \textbf{16}, \textbf{24}, \textbf{29}, \textbf{33}, \textbf{35}, \textbf{39}, .... Note that non-letter characters and spaces are not considered in the formulation of the sequence. When $k \leq 100000$ \textbf{k} \leq \textbf{100000}, it turns out that $\textbf{a_k} \leq \textbf{1000000}$ .

To formulate the sequence, you must be able to write the ordinal numbers in English. The ordinal numbers are $first, second, third, ...$ \textit{\textbf{first}}, \textit{\textbf{second}}, \textit{\textbf{third}}, ..., while the cardinal numbers are $one, two, three, ...$ \textit{\textbf{one}}, \textit{\textbf{two}}, \textit{\textbf{three}}, .... It is easiest to define the ordinals in terms of the cardinals, so we describe these first.

A cardinal number less than twenty is written directly from the first two columns of a table ( $3 \to three$ \textbf{3} \to \textit{\textbf{three}}, $17 \to seventeen$ \textbf{17} \to \textit{\textbf{seventeen}}, etc.). A cardinal number greater than or equal to twenty but less than one hundred is written as the tens part, along with a nonzero ones part ( $40 \to forty$ \textbf{40} \to \textit{\textbf{forty}}, $56 \to fifty six$ \textbf{56} \to \textit{\textbf{fifty six}}, etc.). A cardinal number greater than or equal to one hundred but less than one thousand is written as the hundreds part, along with a nonzero remainder ( $100 \to one hundred$ \textbf{100} \to \textit{\textbf{one hundred}}, $117 \to one hundred seventeen$ \textbf{117} \to \textit{\textbf{one hundred seventeen}}, $640 \to six hundred forty$ \textbf{640} \to \textit{\textbf{six hundred forty}}, $999 \to nine hundred ninety nine$ \textbf{999} \to \textit{\textbf{nine hundred ninety nine}}). A cardinal number greater than or equal to one thousand but less than one million is written as the thousands part, along with a nonzero remainder ( $12345 \to twelve thousand three hundred forty five$ \textbf{12345} \to \textit{\textbf{twelve thousand three hundred forty five}}). An ordinal number is written as a cardinal number, but with the last word ordinalized using the third and fourth columns of a table.

Some example ordinal numbers: $3rd \to third$ \textbf{3rd} \to \textit{\textbf{third}}, $56th \to fifty sixth$ \textbf{56th} \to \textit{\textbf{fifty sixth}}, $100th \to one hundredth$ \textbf{100th} \to \textit{\textbf{one hundredth}}, and $12345th \to twelve thousand three hundred forty fifth$ \textbf{12345th} \to \textit{\textbf{twelve thousand three hundred forty fifth}}.

Input

The input consists of a number of cases. Each case is specified by a positive integer $k$ on one line ( $1 \leq k \leq 100000$ \textbf{1} \leq \textbf{k} \leq \textbf{100000}). The sequence of $k$ values will be non-decreasing. The input is terminated by a line containing a single $0$ .

Output

For each $k$ , print the value of $a_{k}$ a_k on one line. The values of $\textbf{a_k}$ will be at most $1000000$ .

Examples

Example 1