A. Апельсины Лавенсии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После двух долгих холодных лет Рене покидает Лавенсию, имея $$$n$$$ лавенсийских апельсинов и $$$n$$$ изначально пустых мешков для них, причём и апельсины, и мешки пронумерованы от $$$1$$$ до $$$n$$$. Рене раскладывает апельсины согласно массиву $$$a$$$: апельсин $$$i$$$ попадает в мешок $$$a_i$$$.

В Лавенсии действует процедура контроля экспорта. Её проводит Жаклин: она выбирает целое число $$$s$$$ и конфискует все мешки, в которых находится ровно $$$s$$$ апельсинов, причём выбирает такое $$$s$$$, чтобы забрать у Рене как можно больше апельсинов. Стоимостью массива $$$a$$$ называется количество апельсинов, конфискованных Жаклин.

Формально, для заданного массива $$$a$$$ обозначим через $$$c_i$$$ количество элементов, каждое из которых встречается ровно $$$i$$$ раз в массиве $$$a$$$. Стоимость массива $$$a$$$ равна: $$$$$$ \max_{0 \le i \le n} i \cdot c_i $$$$$$

По заданному $$$n$$$ найдите массив $$$a$$$ минимальной стоимости.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите две строки.

В первой строке выведите одно целое число — минимально возможную стоимость.

Во второй строке выведите $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — любой массив, достигающий этой минимальной стоимости.

Пример
Входные данные
3
4
5
8
Выходные данные
2
1 2 3 3
3
1 1 2 2 2
3
4 2 1 5 1 3 1 3
Примечание

В первом наборе входных данных Рене кладёт соответственно $$$1$$$, $$$1$$$, $$$2$$$ и $$$0$$$ апельсинов в четыре мешка. Если Жаклин выбирает число $$$1$$$, она конфискует мешки $$$1$$$ и $$$2$$$, и Рене теряет $$$2$$$ апельсина. Если она выбирает число $$$2$$$, она конфискует мешок $$$3$$$, и он снова теряет $$$2$$$ апельсина. Таким образом, стоимость равна $$$2$$$. Можно доказать, что это минимальная стоимость для данного набора входных данных.

Во втором наборе входных данных в мешке $$$1$$$ находятся $$$2$$$ апельсина, в мешке $$$2$$$ — $$$3$$$, а остальные мешки пусты. При выборе числа $$$2$$$ Рене теряет $$$2$$$ апельсина, а при выборе числа $$$3$$$ — $$$3$$$, поэтому стоимость равна $$$3$$$. Можно доказать, что в этом случае $$$3$$$ — минимальная стоимость.