D. Математическое задание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Математикам 31 лицея было предложено следующее задание:

Вам дано нечетное число $$$n$$$ и вам нужно подобрать $$$n$$$ различных чисел, которые являются квадратами целых чисел. Но не всё так просто. Каждое число должно быть длины $$$n$$$ (и при этом не иметь ведущих нулей) и мультимножество цифр всех чисел должно совпадать. Например, у $$$\mathtt{234}$$$ и $$$\mathtt{432}$$$, $$$\mathtt{11223}$$$ и $$$\mathtt{32211}$$$ мультимножества цифр совпадают, а у $$$\mathtt{123}$$$ и $$$\mathtt{112233}$$$ нет.

Математики не справились с этой задачей, а сможете ли вы?

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Следующие $$$t$$$ строк содержат одно целое нечетное число $$$n$$$ ($$$1 \leq n \leq 99$$$) — количество чисел, которые нужно подобрать и их длина.

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

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

Числа можно выводить в любом порядке.

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

Для каждого набора нужно вывести $$$n$$$ чисел длины $$$n$$$ — ответ на задачу.

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

Пример
Входные данные
3
1
3
5
Выходные данные
1
169
196
961
16384
31684
36481
38416
43681
Примечание

Ниже показано квадратами каких чисел являются ответы для второго набора входных данных:

$$$\mathtt{169}$$$ = $$$\mathtt{13}^2$$$

$$$\mathtt{196}$$$ = $$$\mathtt{14}^2$$$

$$$\mathtt{961}$$$ = $$$\mathtt{31}^2$$$

Ниже показано квадратами каких чисел являются ответы для третьего набора входных данных:

$$$\mathtt{16384}$$$ = $$$\mathtt{128}^2$$$

$$$\mathtt{31684}$$$ = $$$\mathtt{178}^2$$$

$$$\mathtt{36481}$$$ = $$$\mathtt{191}^2$$$

$$$\mathtt{38416}$$$ = $$$\mathtt{196}^2$$$

$$$\mathtt{43681}$$$ = $$$\mathtt{209}^2$$$