eolymp
bolt
Try our new interface for solving problems
Problems

Aronson

Aronson

Time limit 1 second
Memory limit 64 MiB

Aronson's sequence ak 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, .... Note the non-letter characters and spaces are not considered in the formulation of the sequence. When k100000, it turns out that a_k1000000.

To formulate the sequence, you must be able to write the ordinal numbers in English. The ordinal numbers are first, second, third, ..., while the cardinal numbers are one, two, 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 table (3 three, 17seventeen, 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 (40forty, 56fifty 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 (100one hundred, 117one hundred seventeen, 640six hundred forty, 999nine 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 (12345twelve thousand three hundred forty five). An ordinal number is written as a cardinal number, but with the last word ordinalized using the columns three and four of table.

Some example ordinal numbers are 3rdthird, 56thfifty sixth, 100thone hundredth, and 12345thtwelve thousand three hundred forty fifth.

Input data

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

Output data

For each k, print the value of ak on one line. The values of a_k will be at most 1000000.

Examples

Input example #1
1
3
9
0
Output example #1
1
11
39