310977: CF1916D. Mathematical Problem

D. Mathematical Problemtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

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.

ExampleInput

3
1
3
5

Output

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$

题目大意：
第31中学的数学家们被给予了以下任务：给定一个奇数n，需要找到n个不同的整数平方数。每个数的长度为n（不能有前导零），并且所有数的数字组合必须相同。例如，对于234和432，以及11223和32211，数字组合是相同的，但对于123和112233，它们是不同的。数学家们无法解决这个问题，你能解决吗？

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤100）——测试用例的数量。
接下来的t行，每行包含一个奇数n（1≤n≤99）——要找到的数的数量和它们的长度。
保证在给定的约束条件下存在解决方案。
保证n^2的总和不超过10^5。
输出：
对于每个测试用例，你需要输出n个长度为n的数——问题的答案。
如果有多个答案，可以输出其中任何一个。题目大意： 第31中学的数学家们被给予了以下任务：给定一个奇数n，需要找到n个不同的整数平方数。每个数的长度为n（不能有前导零），并且所有数的数字组合必须相同。例如，对于234和432，以及11223和32211，数字组合是相同的，但对于123和112233，它们是不同的。数学家们无法解决这个问题，你能解决吗？ 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤100）——测试用例的数量。 接下来的t行，每行包含一个奇数n（1≤n≤99）——要找到的数的数量和它们的长度。 保证在给定的约束条件下存在解决方案。 保证n^2的总和不超过10^5。 输出： 对于每个测试用例，你需要输出n个长度为n的数——问题的答案。 如果有多个答案，可以输出其中任何一个。