A. World's Hardest Math Problem II
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Note the unusual constraint for n

A number is considered rotationally symmetric if it stays the same when you rotate it $$$180$$$ degrees. In the rotation, digits $$$0, 1, 2, 5,$$$ and $$$8$$$ map onto themselves while $$$6$$$ and $$$9$$$ map onto each other.

In other words, a number is rotationally symmetric if it only contains the digits $$$[0, 1,2,5,6,8,9]$$$, and stays the same when you reverse it and replace its $$$6$$$'s with $$$9$$$'s and $$$9$$$'s with $$$6$$$'s.

For example, the number $$$2112$$$ is rotationally symmetric as shown:

$$$5115$$$, $$$2650592$$$, and $$$88$$$ are all rotationally symmetric, while $$$25$$$, $$$66$$$, and $$$33$$$ are not.

Given a number $$$n$$$ ($$$2 \leq n \leq 6$$$), output an $$$n$$$-digit rotationally symmetric number that is divisible by $$$3$$$.

Input

The first line contains one integer: $$$n$$$ ($$$2 \leq n \leq 6$$$)

Output

Output an $$$n$$$ digit rotationally symmetric number that is divisible by 3. Note that leading zeros don't count as digits, so $$$00$$$ would NOT be a valid answer if $$$n=2$$$.

Example
Input
3
Output
111
Note

Hint: A number is divisible by $$$3$$$ if the sum of its digits is divisible by $$$3$$$.