很快，新的手机服务提供商“BerLine”将在 Berland 开始运营！

计划在首都的主干道上开始客户服务。已经安装了 $n$ 个基站。它们从左到右依次排列在主干道上，顺序为第 $1$ 个到第 $n$ 个。

目前，所有这些基站都处于关闭状态。它们将根据某个排列 $p = [p_1, p_2, \dots, p_n]$ ($1 \le p_i \le n$) 逐个开启，每天开启一个基站，其中 $p_i$ 是第 $i$ 天开启的基站索引。因此，开启所有基站需要 $n$ 天。

每个基站的特征是其工作频率 $f_i$ —— 一个 $1$ 到 $24$ 之间的整数（包含 $1$ 和 $24$）。

基站的工作频率有一个重要的要求。考虑任意时刻。对于任何手机用户，如果我们考虑其覆盖范围内所有已开启的基站，那么在这些基站的集合中，至少应该有一个基站的工作频率在这些基站中是唯一的。由于手机的功率和位置无法预先得知，这意味着对于任何已开启基站的非空子段，其中至少有一个基站的频率在该子段的基站中是唯一的。

例如，让我们看一个 $n = 7$ 的情况，所有 $n$ 个基站都已开启，它们的频率为 $f = [1, 2, 1, 3, 1, 2, 1]$。考虑基站的任何子段，该子段内都有一个频率唯一的基站。然而，如果 $f = [1, 2, 1, 2, 3, 2, 1]$，则在从索引 $1$ 到索引 $4$（包含）的段 $[1, 2, 1, 2]$ 上没有唯一的频率。

你的任务是为每个基站分配一个 $1$ 到 $24$ 之间的频率，使得频率要求在任何时刻都能得到满足。请记住，基站是按照给定的排列 $p$ 的顺序开启的。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 50$) —— 输入中的测试用例数量。 接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 8\,500$) —— “BerLine”基站的数量。 下一行包含 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) —— 基站开启的顺序，即第 $i$ 天开启索引为 $p_i$ 的基站。

保证输入的所有测试用例都有正确答案。

输出格式

打印 $t$ 行，其中第 $j$ 行包含输入中第 $j$ 个测试用例的答案。打印所需的频率 $f_1, f_2, \dots, f_n$ ($1 \le f_i \le 24$)。如果有多种可能的答案，打印其中任何一个即可。

样例

输入 1

5
3
1 3 2
3
1 2 3
1
1
10
6 10 4 2 7 9 5 8 3 1
10
2 4 6 9 1 8 10 5 3 7

输出 1

1 3 2
10 20 10
1
2 3 4 5 3 1 3 5 4 2
1 2 3 4 5 6 7 8 9 10

说明

在第一个测试用例中，$n = 3$ 且 $p = [1, 3, 2]$。基站可以被分配频率 $[1, 3, 2]$。

• 第 1 天：只有基站 1 开启，其频率为 1。
• 第 2 天：基站 1 和 3 开启，它们的频率为 $[1, 2]$。
• 第 3 天：所有基站开启，它们的频率为 $[1, 3, 2]$（沿街道方向）。

在每一天，每个已开启基站的非空子段都有一个在该子段中频率唯一的基站。可以证明，在这个测试用例中，需要三种不同的频率。