A cycle is a connected undirected graph with n vertices of degree 2. (Special cases: The cycle for n = 2 is a graph with two vertices and two parallel edges between them. For n = 1 the cycle is a graph with a single vertex and a loop. In all cases, you can imagine the cycle as a circle passing through n locations.)

The distance d of two vertices is the number of edges on the shortest path that connects them.

A labelling of a cycle is a function f that assigns a positive integer to each of its vertices.

Given a labelling, we may pick a starting vertex and direction along the cycle and write down the labels in the order in which we encounter them. The n-tuple obtained in this way is called a label list.

There may be multiple label lists corresponding to a single labelling. For example, the label lists (3,8,25,14,17) and (25,8,3,17,14) may come from the same labelling.

A labelling is called jumpy if it has the following properties:

• No two labels are equal.
• For each pair of distinct vertices u,v the greatest common divisor of f(u) and f(v) is at most d(u,v).

(In other words, neighboring vertices must have relatively prime labels, vertices at distance 2 may only have 2 as the common divisor of their labels, etc.)

For example, a cycle with the label list (3,8,25,14,17) is a jumpy cycle.

The upper bound of a labelling is the largest integer it uses.

Given two distinct label lists of a given cycle, look at the first position where they differ. The one with the smaller value on this position is lexicographically smaller.

Task

Given is the number of vertices n. Find a jumpy labelling of a cycle with n vertices with the smallest possible upper bound. If there are multiple such labellings, pick the one that can produce the lexicographically smallest label list.

Input

Ignore the input.The file's empty, anyway.

Output

For each n from 1 to 20 output a single line with a sequence of n positive integers: the lexicographically smallest label list that determines a jumpy labelling with the smallest possible upper bound. Separate the integers by single spaces. (Do not print a space after the last integer on a line.)

Example

Input:


Output:

1
... and 19 more lines ...