Дано целое число $$$n$$$. Рассмотрим массив $$$a = [1, 2, \ldots, n]$$$. Вы можете выбрать любые его элементы и умножить каждый из выбранных элементов на $$$2$$$. Каждый элемент можно удвоить не более одного раза. Можно выбирать любые элементы, в том числе выбрать все или не выбрать ни одного. Получившийся массив обозначим через $$$b$$$.
Пусть $$$k$$$ — побитовое ИЛИ всех элементов исходного массива $$$a$$$, а $$$m$$$ — побитовое исключающее ИЛИ всех элементов получившегося массива $$$b$$$:
$$$$$$ k = a_1 \mathbin{|} a_2 \mathbin{|} \cdots \mathbin{|} a_n, \qquad m = b_1 \oplus b_2 \oplus \cdots \oplus b_n. $$$$$$
Выберите элементы для удвоения так, чтобы выполнялось $$$m \ge 2k$$$. Можно показать, что при любом допустимом $$$n$$$ это возможно. Минимизировать количество удвоенных элементов не требуется.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину массива.
Дополнительные ограничения на входные данные:
Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$. Каждое $$$d_i$$$ должно быть равно $$$0$$$ или $$$1$$$: если $$$d_i = 1$$$, элемент $$$a_i$$$ нужно удвоить, а если $$$d_i = 0$$$ — оставить без изменения.
Если подходящих ответов несколько, выведите любой из них.
5369511
1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1
В первом наборе входных данных $$$k = 3$$$. После удвоения выбранных элементов $$$b = [2, 2, 6]$$$ и $$$m = 6$$$.
Во втором наборе входных данных $$$k = 7$$$. После удвоения выбранных элементов $$$b = [1, 4, 6, 4, 5, 12]$$$ и $$$m = 14$$$.
