Với một mảng ~x~ bất kỳ được tạo bởi ~n~ số nguyên dương, ta định nghĩa điểm của mảng ~x~ là

$$\max_{1 \le i < j \le n} \operatorname{LCP}(x_{i:n}, x_{j:n})$$

với ~x_{l:r}~ là mảng con ~[x_l, x_{l + 1}, \ldots, x_r]~ của ~x~, và ~\operatorname{LCP}(b, c)~ trả về độ dài tiền tố chung dài nhất của hai mảng ~b~ và ~c~.

Cho mảng ~a~ gồm ~n~ số nguyên dương. Hãy sắp xếp lại mảng ~a~ sao cho điểm của mảng là lớn nhất có thể.

~\operatorname{LCP}(b, c)~ là hàm trả về ~i - 1~ với ~1 \le i \le \min(|b|, |c|)~ là vị trí đầu tiên sao cho ~b_i \neq c_i~, hoặc trả về ~\min(|b|, |c|)~ nếu vị trí này không tồn tại.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10^5~). Mô tả của mỗi test case như sau.

Dòng đầu tiên của mỗi test case chứa một số nguyên ~n~ (~2 \le n \le 5 \cdot 10^5~) — độ dài của mảng ~a~.

Dòng thứ hai của mỗi test case chứa ~n~ số nguyên dương ~a_1, \ldots, a_n~ (~1 \le a_i \le n~) – các phần tử của mảng ~a~.

Đảm bảo rằng tổng của ~n~ qua mọi test case không vượt quá ~5 \cdot 10^5~.

Output

Với mỗi test case, hãy in ra hai dòng.

Dòng đầu tiên in ra một số nguyên là số điểm lớn nhất có thể đạt được sau khi sắp xếp các phần tử của ~a~.

Dòng thứ hai in ra ~n~ số nguyên ~a^\prime_1, a^\prime_2, \ldots, a^\prime_n~, với ~a^\prime~ là mảng có thể thu được khi sắp xếp lại các phần tử của mảng ~a~ để thu được số điểm lớn nhất.

Nếu tồn tại nhiều cách sắp xếp mảng để thu được số điểm lớn nhất có thể, hãy tìm một cách bất kỳ.

Scoring

Sample Input 1

6
7
1 3 2 2 1 4 3
7
1 3 2 2 1 4 1
4
1 2 3 4
9
6 6 9 9 6 9 9 9 9
13
11 7 12 7 12 12 12 4 12 7 7 4 7
10
2 1 1 9 1 9 1 2 1 1

Sample Output 1

3
1 3 2 4 1 3 2
3
4 1 2 1 2 1 3
0
1 2 3 4
6
9 6 9 9 6 9 9 6 9
8
11 4 7 12 7 12 7 12 7 12 7 12 4
6
1 1 2 9 1 1 2 9 1 1

Sample Input 2

3
5
1 1 1 1 2
6
2 1 2 1 1 1
32
1 2 1 2 1 2 2 1 1 2 1 1 1 1 2 2 1 1 2 2 1 1 2 1 1 1 2 2 1 2 1 2

Sample Output 2

3
2 1 1 1 1 
3
2 2 1 1 1 1 
27
1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

Notes

• Ở test case thứ nhất, điểm của mảng ~[1, 3, 2, 4, 1, 3, 2]~ là ~3~, vì nếu ta lấy ~i = 1~ và ~j = 5~ thì $$\operatorname{LCP}(a_{i:n}, a_{j:n}) = \operatorname{LCP}([1, 3, 2, 4, 1, 3, 2], [1, 3, 2]) = 3$$ và không có cặp ~i~ và ~j~ nào cho ra kết quả cao hơn. Đây cũng là số điểm tối đa có thể đạt được của bất kỳ cách sắp xếp nào của ~a~. Một cách sắp xếp khác cho ra số điểm là ~3~ là ~[4, 3, 2, 1, 3, 2, 1]~.

• Ở test case thứ hai, điểm của mảng ~[4, 1, 2, 1, 2, 1, 3]~ là ~3~, do với ~i = 2~ và ~j = 4~ thì $$\operatorname{LCP}(a_{i:n}, a_{j:n}) = \operatorname{LCP}([1, 2, 1, 2, 1, 3], [1, 2, 1, 3]) = 3$$

• Ở test case thứ ba, bất kỳ cách sắp xếp nào cũng cho ra số điểm bằng ~0~.