For the purposes of this problem, a permutation of length $$$n$$$ is an array of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$.
You are given a permutation $$$p = (p_1, p_2, \ldots, p_n)$$$ of the integers $$$1$$$ through $$$n$$$.
You are to color its elements using the minimum possible number of colors so that there is no pair of indices $$$(i, j)$$$ such that the following conditions hold at the same time:
If there are several valid colorings with the minimum possible number of colors, find any of them.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$): the number of test cases. Then, $$$t$$$ test cases follow.
The first line of a test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$): the length of the permutation.
The second line of a test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). It is guaranteed that each integer from $$$1$$$ to $$$n$$$ appears exactly once.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print two lines.
In the first line, print a single integer $$$k$$$ ($$$1 \leq k \leq n$$$): the minimum possible number of colors.
In the second line, print $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq k$$$), where $$$c_i$$$ is the color of the $$$i$$$-th element of the permutation. Each color from $$$1$$$ to $$$k$$$ must be used at least once. Any optimal valid coloring will be accepted.
353 1 4 2 544 3 2 131 2 3
31 1 2 2 311 1 1 131 2 3
| Name |
|---|


