Description

给定一个数组 $A = [a_1, a_2, \dots, a_n]$，其中包含 $n$ 个正整数。

需要将数组元素涂成两种颜色，使得任意两个同一颜色的元素 $x$ 和 $y$ 不满足以下条件：

• $x=p\times y$，其中 $p$ 是一个素数。

保证存在这样的涂色方案。

Input Format

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示数组的元素个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^6$），即数组中的元素。

Output Format

输出数组的划分方案。具体地，输出一行 $n$ 个整数，如果第 $i$ 个数字为 $1$，表示第 $i$ 个元素应涂成第一种颜色；如果为 $2$，则表示第 $i$ 个元素应涂成第二种颜色。

如果存在多个合适的划分方案，可以输出其中任何一个。

4
1 2 3 4

2 1 1 2

1
20

1

Hint

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^6$。