The special April contests have just ended, but the problem setters are still marveling over the yearly event.

For example, a Fool's number is an attractive positive integer. A Fool's number has the interesting property that, in its decimal representation, it is possible to insert spaces to form a series of 's and 's, without any other additional garbage.

A problem setter defines the Fool's sequence, which contains every Fool's number in strictly increasing order, with no additional terms that are not Fool's numbers (what is the fun if the term is ?). The first term is and the second term is .

However, the sequence grows quite strangely, and it is hard to list the sequence! What is the term of the Fool's sequence? Since there is no point in knowing just one term, you want to repeat this process times in total.

#### Constraints

In all subtasks, .

Subtask | Points | |
---|---|---|

1 | 5 | |

2 | 15 | |

3 | 40 | |

4 | 20 | |

5 | 20 |

#### Input Format

The first line contains one integer, .

The next lines contain a single integer, .

#### Output Format

Output the term of the Fool's sequence on a new line.

#### Sample Input

```
2
3
5
```

#### Sample Output

```
6969
69420
```

#### Explanation for Sample Output

The first terms of the Fool's sequence are:

The term of the sequence is .

The term of the sequence is .

## Comments