When little Limak played with numbers he noticed a surprising property:
If two numbers are coprime, they like each other and want to spend time together.
Otherwise, they hate each other and cannot be together.
Limak has a good heart and he wants numbers to be happy.
You are given an int N.
Limak asks you to find a sequence of N integers t, t, ..., t[N-1] with following properties:
- Every element should be between 1 and 10^18, inclusive.
- Each pair of consecutive elements must be coprime. In other words, for every i between 0 and N-2, inclusive, the greatest common divisor of t[i] and t[i+1] must be 1.
- No other pairs of elements may be coprime. In other words, for every valid i and j such that i + 2 ? j the numbers t[i] and t[j] must have a common divisor greater than one.
Find any such sequence and return it as a long.
(You may assume that for the given constraints a solution always exists.)