Generate Array with Perfect Square Sum

You are given an integer n. Your task is to generate an array of integers as follows:

• First, form an array consisting of the first n positive integers: \(1,2,\ldots,n\).
• Let \(S\) be the sum of the array, that is \(S = 1+2+\ldots+n\).
• If \(S\) is already a perfect square, print the array.
• If \(S\) is not a perfect square, find the smallest positive integer \(k\) (starting from 1) such that \(S+k\) becomes a perfect square, then append \(k\) to the array and print the resulting array.

Note: A perfect square is an integer that can be expressed as \(m^2\) for some integer \(m\). The output array may contain a repeated element if the appended integer \(k\) is already present in the initial list.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains a single integer \(n\) representing a test case.

outputFormat

For each test case, output the generated array of integers in one line, with each element separated by a space.

## sample

4
1
2
3
4

1
1 2 1
1 2 3 3
1 2 3 4 6

</p>