The mayor is preparing for the arrival of the ICPC participants. On their tour, they will pass by n towers, each with a distinct height.
The architects designed these towers in a special way. The towers are aligned in a single line and numbered from 1 to n from left to right. Each of them is connected by a bridge to the closest tower to its left with a greater height, if one exists, and also by another bridge to the closest tower to its right with a greater height, if it exists.
The mayor doesn't want to make their tour boring. Therefore in preparation, he wants to color the n towers such that there is no bridge that connects two towers of the same color.
Help the mayor find a valid way to color the n towers with the minimum number of colors.
The first line of input contains a single integer T (1 ≤ T ≤ 128), the number of test cases.
The first line of each test case contains a single integer n (1 ≤ n ≤ 106), the number of towers.
The second line contains n space-separated distinct integers (1 ≤ hi ≤ 109), the ith integer represents the height of the ith tower.
The sum of n over all test cases doesn't exceed 5 × 106.
For each test case, output two lines. The first line should contain the minimum number of colors k needed to color the towers.
The second line should contain n space-separated integers that represent a valid way to color the towers. The ith integer is the color of the ith tower, and it must be between 1 and k (inclusive).
If there are multiple valid ways, print any of them.
1
5
7 1 9 5 2
3
2 3 1 2 1
In the first sample test, the pairs of towers connected by bridges are: (1, 2), (1, 3), (2, 3), (3, 4), and (4, 5).
