H. Равномерное кодирование
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компания Naudio планирует создание и выпуск нового производительного процессора для обработки аудио-данных. Набор команд процессора должен содержать $$$K$$$ команд.

Каждая команда процессора — двоичная строка некоторой фиксированной длины $$$Len$$$. Вам поручено определить кодировку каждой из $$$K$$$ команд, то есть определить их двоичный вид, соблюдая следующие условия:

  1. (Запатентованная фишка) Длина $$$Len$$$ должна быть четной;
  2. (Корректность работы) Все команды должны быть различны между собой;
  3. (Контроль качества передачи) Каждая команда должна содержать одинаковое число единичных бит;
  4. (Равномерный отвод тепла) Количество строк, содержащих каждый бит, должно отличаться не более чем на $$$1$$$.

    Формально, пусть $$$i$$$ и $$$j$$$ $$$(1 \leq i, j \leq len)$$$ — номера каких-то бит в команде. Тогда $$$|cnt_k(i) - cnt_k(j)| \leq 1$$$ для любой пары $$$i, j$$$.

    Здесь $$$cnt_k(i)$$$ определяется как количество команд, в которых $$$i$$$-й бит был равен единице.

  5. (Оптимизация памяти) Среди всех возможных кодировок, удовлетворяющих условиям выше, выберите ту, в которой длина $$$Len$$$ минимально возможная.
Входные данные

В первой строке входные данных содержится одно целое число $$$T$$$ ($$$1 \leq T \leq 10$$$) — количество прототипов процессора.

Каждая из следующих $$$T$$$ строк состоит из одного целого числа $$$K_i$$$ ($$$1 \leq K_i \leq 10^4$$$) — требуемого количества команд в наборе команд $$$i$$$-го прототипа процессора Naudio.

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

Для $$$i$$$-го прототипа выведите:

  • В первой строке одно целое четное число $$$Len$$$ $$$(2 \le Len \le 100)$$$  — минимальную длину, которую можно использовать для построения $$$K_i$$$ различных команд, удовлетворяющих всем условиям;
  • Во второй строке через пробел выведите $$$K_i$$$ двоичных строк $$$S_j$$$ $$$(|S_j| = Len)$$$ — различные команды длины $$$Len$$$.

Если корректных ответов несколько, выведите любой.

Гарантируется, что ответ всегда существует в заданных ограничениях задачи.

Пример
Входные данные
3
1
2
3
Выходные данные
2
01
2
01 10
4
1110 1101 0111
Примечание

Первый прототип

В данном случае необходима одна команда.

Минимальная подходящая длина $$$Len$$$ равна $$$2$$$ (т.к. она обязана быть четной).

Всего возможно четыре варианта:

  • 00
  • 01
  • 10
  • 11

Можно вывести любую из них.

Второй прототип

Длина и набор возможных команд аналогичен первому прототипу.

В то же время подходит только пара команд 01 и 10 (в любом порядке), так как любая другая пара команд будет различаться по количеству единичных бит.

Третий прототип.

В данном случае длины $$$2$$$ уже не хватит, поэтому $$$Len = 4$$$.

Каждая из использованных команд содержит ровно $$$3$$$ единичных бита.

Рассмотрим, сколько команд содержат каждый бит:

  • $$$count(1) = 2$$$ — команды 1110 и 1101;
  • $$$count(2) = 3$$$ — команды 1110, 1101 и 0111;
  • $$$count(3) = 2$$$ — команды 1110 и 0111;
  • $$$count(4) = 2$$$ — команды 1101 и 0111.

Видно, что количество команд с каждым битом отличается не более, чем на 1.