D. Mathematical Problem
brute force; constructive algorithms; geometry; math
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.
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\)