题目描述

给定一个数组 $a_1, a_2, ..., a_n$。你需要找到一个数组 $b_1$, $b_2$, ..., $b_n$，其中包含数字 $1, 2, 3$，使得以下三个条件中恰好有两个条件被满足：

• 存在 $1\le i, j\le n$，使得 $a_i=a_j,b_i=1,b_j=2$。
• 存在 $1\le i, j\le n$，使得 $a_i=a_j,b_i=1,b_j=3$。
• 存在 $1\le i, j\le n$，使得 $a_i=a_j,b_i=2,b_j=3$。

如果不存在这样的数组 $b$，请报告不可以。

输入格式

每个测试点多测。第一行输入一个整数 $t$，表示数据组数。对于每一组数据：

第一行输入一个整数 $n$ $(1\le n\le 100)$，表示数组 $a$ 的长度。

第二行读入 $n$ 个整数 $a_1,a_2,...,a_n$ $(1\le a_i\le 100)$，代表数组 $a$。

输出格式

对于每组数据输出一行。若无解，则输出 -1。否则输出一个由 $1,2,3$ 组成的数组 $b$，恰好满足两条性质。如果有多个合法数组，输出任一即可。

说明/提示

第一个数组 $a$，合法数组可以是 $b=[1,2,3,1,1,1]$。当 $i = 4,j = 2$ 时，满足性质一。当$i = 6,j = 3$ 时满足性质二。数组 $b$ 无法满足性质三，所以恰好满足两条，合法。

样例

9
6
1 2 3 2 2 3
7
7 7 7 7 7 7 7
4
1 1 2 2
7
1 2 3 4 5 6 7
5
2 3 3 3 2
3
1 2 1
9
1 1 1 7 7 7 9 9 9
1
1
18
93 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69

1 2 3 1 1 1 
-1
3 2 2 1 
-1
2 1 2 1 3 
-1
1 1 2 2 1 2 2 3 3
-1
3 2 1 3 3 3 3 2 2 1 1 2 3 1 3 1 1 2