There are $n$ water lilies, numbered $1$ through $n$, in a line. On the $i^{\text{th}}$ lily there is a positive integer $x_i$, and the sequence $(x_i{)}_{1\le i\le n}$ is strictly increasing.

Enter three frogs.

Every pair of water lilies $(a,b)$, where $a<b$, must belong to frog $1$, frog $2$, or frog $3$.

A frog can hop from water lily $i$ to water lily $j>i$ if the pair $(i,j)$ belongs to it, and $x_i$ divides $x_j$.

Distribute the pairs among the frogs such that no frog can make more than $3$ consecutive hops.

Input Specification

The first line contains a positive integer $n$ $(1\le n\le 1000)$, the number of water lilies.

The second line contains $n$ positive integers $x_i$ $(1\le x_i\le {10}^{18})$, the numbers on the water lilies.

Output Specification

Output $n-1$ lines. In the $i^{\text{th}}$ line, output $i$ numbers, where the $j^{\text{th}}$ number is the label of the frog to which $(j,i+1)$ belongs.

Constraints

Subtask	Points	Constraints
$1$	$10$	$n\le 30$
$2$	$100$	No additional constraints.

If in your solution some frog can make $k$ consecutive hops, where $k>3$, but no frog can make $k+1$ consecutive hops, your score for that test case is $f(k)\cdot x$ points, where

$${\displaystyle f(x)=\frac{1}{10}\cdot \{\begin{array}{ll}11-k& \text{if }4\le k\le 5\\ 8-\lfloor k/2\rfloor & \text{if }6\le k\le 11\\ 1& \text{if }12\le k\le 19\\ 0& \text{if }k\ge 20\end{array}}$$

and $x$ is the number of points for that subtask.

The score for some subtask equals the minimum score which your solution gets over all test cases in that subtask.

Sample Input 1

8
3 4 6 9 12 18 36 72

Sample Output 1

1
2 3
1 2 3
1 2 3 1
2 3 1 2 3
1 2 3 1 2 3
1 2 3 1 2 3 1

Explanation

The frogs are marked blue ($1$), green ($2$), and red ($3$).

The blue frog can hop from water lily $x_1=3$ to water lily $x_4=9$, then to water lily $x_7=36$, and then to $x_8=72$. These are the only three consecutive hops any frog can make.

The green frog can hop from water lily $x_2=4$ to water lily $x_5=12$, and then to $x_7=36$, because $4$ divides $12$, and $12$ divides $36$. Those are two consecutive hops.

The red frog cannot hop from water lily $x_2=4$ to water lily $x_3=6$ because $6$ is not divisible by $4$.

No frog can make more than three consecutive hops.

Sample Input 2

2
10 101

Sample Output 2

1