You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time limit: 4.0 seconds

Memory limit: 256 megabytes

We worship perfection because we can't have it; if we had it, we would reject it. ——The Book of Disquiet, Poet, Fernando Pessoa

题目描述

傅猫猫是一只很长的猫猫,为此它希望它生活中的一切东西都尽量得长来与它相适配,这当然也包括了它爪机中的锁屏图案.

傅猫猫爪机中的图案锁屏与人类的手机中的相同: 一共三行三列共$9$个点,同行同列的点间距相同.

在本题中我们从上到下,从左到右依次给他们编号$1-9$,如图:

你需要选择全部的$9$个点(每个点只能被选择$1$次),最终通过线段将它们顺次连接,以此来绘制锁屏图案.

注意,如果你将两点连线时经过了一个未被经过的点,则这种连线方式无效. 如:$1\quad3\quad2$:你在连接$1$和$3$时没有经过$2$这个点,那么你在连接$1$和$3$时手机会自动帮你连上2. 但是$2 \quad 1 \quad 3$这种连线方式则是合法的.

连完之后你可以得到一个编号序列,如"$5 \quad 9 \quad 1 \quad 8 \quad 2 \quad 7 \quad 3 \quad 4 \quad 6$"就代表了一个这样的锁屏图案:

不妨设同行的点间距为$1$,这样你的手指就需要在屏幕上移动:

$\sqrt{2} + 2\sqrt{2} + \sqrt{5} + 2 + \sqrt{5} + 2\sqrt{2} + \sqrt{5} + 2 = 4 + 5\sqrt{2} + 3\sqrt{5}$

的距离,可以证明这个编号序列是最长的锁屏图案.

傅猫猫想知道第$k$长的锁屏图案的编号序列.

我们规定: 长度相同的锁屏图案,编号序列的字典序小的要更短,即我们比较两个编号序列中第一个不同的数字,数字小的字典序小. 如$5 \quad 9 \quad 1 \quad 8 \quad 2 \quad 7 \quad 3 \quad 4 \quad 6$和$5 \quad 9 \quad 1\quad 6 \quad 4 \quad 3 \quad 7 \quad 2 \quad 8$都具有相同的长度,但是它们第一个不同数字前一个为$8$,后一个为$6$,因此后一个要比前一个短.

输入

输入一共$T(1 \leq T \leq 2*10^5)$组. 每组第一行有$1$个整数$k$.代表傅猫猫想知道的第$k$长的锁屏图案是什么.

输入保证$k$合法.

输出

每组输出一行共$9$个整数代表第$k$长的锁屏图案的编号序列.

5
1
114
514
666
140704

5 9 1 8 2 7 3 4 6
5 1 9 4 2 8 3 7 6
4 9 5 3 7 2 8 1 6
6 1 8 5 3 7 2 9 4
1 2 3 6 5 4 7 8 9

Postscript

For someone special: If I should meet thee After long years, How should I greet thee? — With silence and tears.