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[0], t[1], ..., 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.) |