codeforces#P1916D. Mathematical Problem

    ID: 34318 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>brute forceconstructive algorithmsmath*1700

Mathematical Problem

Description

The mathematicians of the 31st lyceum were given the following task:

You are given an odd number $n$, and you need to find $n$ different numbers that are squares of integers. But it's not that simple. Each number should have a length of $n$ (and should not have leading zeros), and the multiset of digits of all the numbers should be the same. For example, for $\mathtt{234}$ and $\mathtt{432}$, and $\mathtt{11223}$ and $\mathtt{32211}$, the multisets of digits are the same, but for $\mathtt{123}$ and $\mathtt{112233}$, they are not.

The mathematicians couldn't solve this problem. Can you?

The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The following $t$ lines contain one odd integer $n$ ($1 \leq n \leq 99$) — the number of numbers to be found and their length.

It is guaranteed that the solution exists within the given constraints.

It is guaranteed that the sum of $n^2$ does not exceed $10^5$.

The numbers can be output in any order.

For each test case, you need to output $n$ numbers of length $n$ — the answer to the problem.

If there are several answers, print any of them.

Input

The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The following $t$ lines contain one odd integer $n$ ($1 \leq n \leq 99$) — the number of numbers to be found and their length.

It is guaranteed that the solution exists within the given constraints.

It is guaranteed that the sum of $n^2$ does not exceed $10^5$.

The numbers can be output in any order.

Output

For each test case, you need to output $n$ numbers of length $n$ — the answer to the problem.

If there are several answers, print any of them.

3
1
3
5
1
169
196
961
16384
31684
36481
38416
43681

Note

Below are the squares of the numbers that are the answers for the second test case:

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

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

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

Below are the squares of the numbers that are the answers for the third test case:

$\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$