Nine Out Of Ten
time limit per test
1 second
memory limit per test
1024 mebibytes
input
standard input
output
standard output

A mad scientist conducted $$$n$$$ independent identical experiments and claimed that $$$x$$$ of them were successful. It is well known that the mad scientist is wrong in exactly 90% of cases when determining the success of a single experiment. Your task is to write a program that calculates the minimum and the maximum possible number of successful experiments for all $$$x$$$ from $$$0$$$ to $$$n$$$. It is guaranteed that the total number of experiments is always divisible by $$$10$$$.

Input

The first line contains a single integer $$$n$$$, which is a multiple of ten ($$$10 \le n \le 10\,000$$$).

Output

Print $$$n + 1$$$ lines. On the $$$i$$$-th line, output two integers separated by a space: the minimum and the maximum possible number of successful experiments for $$$x = i - 1$$$.

Example

Input

    10

Output

    9 9
    8 10
    7 9
    6 8
    5 7
    4 6
    3 5
    2 4
    1 3
    0 2
    1 1