Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Mischievous Meme Maker

By Sherlock221b · Limits 1s, 512 MB

Memes are love, memes are life. Living in 2018, we are all very familiar with internet memes. They are our favourite procrastination tools. Have you seen one of those memes floating around your feed where there is a list of crimes and a point assigned to each of those crime? What it asks you to do is to add the points of all the crimes you have committed and post the total.


Now you run a meme page on your favourite social platform BaceFook and you’ve decided to play a prank on your subscribers. You want to create a meme where there will be exactly N crimes listed and a point assigned to each of them. But whenever someone comments their total point, you want to be able to tell exactly which crimes they have committed (because you get your kick out of knowing what random people on the internet are up to). Your task in this problem is to assign points to each of the crimes of your meme. If there are multiple possible solutions, choose the one where the total sum of all points is minimized. If there are multiples solutions with the lowest total sum, you can print any of them. But make sure that all the points are positive integer and sorted in non-decreasing order.

For example, let’s consider you have N = 2 crimes in your meme. If you assign 1 point to the first crime and 2 points to the second crime, you can uniquely identify the set of crimes someone has committed from their answer. If the sum is 0, that person hasn’t done anything (obviously). If the sum is 1, that person has committed the first crime only. If the sum is 2, that person has committed the second crime only. If the sum is 3, that person has committed both the first and the second crime. Note that you could also achieve your objective by assigning, let’s say, 4 to the first crime and 10 to the second crime. But since you have to minimize the total sum of all the points, this solution is not valid. In our solution, the total sum is 3, and it can be shown that no such arrangement is possible with a lower total sum.

Input

The first line of the input contains a positive integer T (1 ≤ T ≤ 50) denoting the number of test cases. Each of the next T line contains a single integer N (1 ≤ N ≤ 50) denoting the number of crimes in your meme.

Output

For each of the T test cases, print N numbers in a single line. The i-th of these numbers denote the point assigned to the i-th crime (1 ≤ i ≤ N). All the points have to be positive integers and printed in non-decreasing order. Again, if there are multiple possible solutions, choose the one where the total sum of all points is minimized. If there are multiples solutions with the lowest total sum, you may print any of them.

Sample

InputOutput
2
1
2
1
1 2

For test case 1, you only have one crime in your meme and therefore the solution is to assign 1 point to that crime.

Test case 2 is explained in the problem description.

Discussion

Statistics


82% Solution Ratio

SuperstormEarliest, Jul '18

syed_jafrulFastest, 0.0s

SuperstormLightest, 131 kB

mdgaziur001Shortest, 77B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.