You are given two positive integers $x$ and $y$. The following four operations can be performed with a cost of 1 any number of times:

• Add 1 to $x$.
• Add 1 to $y$.
• Subtract 1 from $x$.
• Subtract 1 from $y$.

You need to find the minimum total cost to make these two integers have no common divisors greater than 1.

Foammm needs to generate some test cases for the problem. She gives you an integer $k$, and you need to find two positive integers $x$ and $y$ so that the answer to the above problem is exactly $k$.

Illustration of the operation process

Input

There is only one test case in each test file.

The first and only line contains an integer $k$ ($0 \le k \le 20$).

Output

Output an integer $x$ ($0 < x < 10^{1500}$) in the first line, followed by an integer $y$ ($0 < y < 10^{1500}$) in the second line.

It can be shown that the answer always exists. If there are multiple valid answers, you can output any of them.

Examples

Input 1

0

Output 1

1
1

Input 2

1

Output 2

2
2

Input 3

2

Output 3

945
1210

Note

Two integers are said to have no common divisors greater than 1 if their greatest common divisor (GCD) is 1. In other words, they are coprime. The cost to change $x$ to $x'$ and $y$ to $y'$ is $|x - x'| + |y - y'|$. You want to minimize this cost such that $\gcd(x', y') = 1$.