Simone, a student of Graph Coloring University, is interested in permutation. Now she is given a permutation of length , and she finds that if she connects each inverse pair, she will get a graph. Formally, for the given permutation, if  and , then there will be an undirected edge between node  and node  in the graph. 

Then she wants to color this graph. Please achieve poor Simone's dream. To simplify the problem, you just need to find a way of coloring the vertices of the graph such that no two adjacent vertices are of the same color and minimize the number of colors used.

输入描述:

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. 

For each test case, the first line contains an integer , indicating the length of the permutation. 

The second line contains  integers , indicating the permutation.

It is guaranteed that the sum of  over all test cases does not exceed .

输出描述:

For each test case, the first line contains an integer , the chromatic number(the minimal number of colors been used when coloring) of the graph.

The second line contains  integers , the color of each node.

Notice that  should satisfy the limit that .

If there are several answers, it is acceptable to print any of them.

2
4
1 3 4 2
2
1 2

2
1 1 1 2 
1
1 1