SP1483 PT07G - Colorful Lights Party

ACRush and his friends want to open a party to celebrate the good result of THU in ICPC 2007. They will use all halls in THU for their party. There are 2 kinds of hall: the small and the large one. In each hall, there is an electronic light system, which forms a tree topology to reduce redundant wires. - In a small hall, the light system is a general tree with n lights. The lights are numbered from 1 to _n_ - In a large hall, the light system is obtained from _k_ chains of lights, each chain has length _t_. The first lights of these k chains are connected with a big light at the central stage of the hall. The big light has id 1, the first light of each chain has id from 2 to k+1, then we continue with the second light of each chain, so on... Take a look at the figure below:  ACRush hopes in every hall, each light has an unique color and so do the wires! For easier to remember and to hang up lights against the walls, he sets a rule: - For each hall, we number the color from 0 to _n-1_, so each light will get a color id in set {0, 1, ..., _n-1_}. - Color id of the wire connects i-th light and j-th light uniquely identified by the positive difference between color ids of i-th light and j-th light. At first view, the rule seems easy, so everyone agrees with him. But it's really tough if the room is quite large, too hard to set colors for lights. After few seconds, ACRush says _"So in this hall, the 1-st light should have color 3, the 2-nd one should have color 0,..."_. Well, how can he do it very fast? How about you ? Let write a program to help ACRush's friends setting colors for lights in all _T_ halls.

The first line of file is _T_ -- number of halls in THU (0 < T

For each hall, show us _n_ numbers on one line, i-th number is the color id of i-th light. If there are many solutions any of them will be accepted. Otherwise, if there is no solution, all color id should be _-1_. The color ids on one line are separated by exactly one blank, and you'd better not print any redundant blanks. There is no blank line after each case.