汉诺塔Ⅰ

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

古老的汉诺塔问题是:用最少的步数将N个半径互不相等的圆盘从1号柱利用2号柱全部移动到3号柱,在移动的过程中小盘要始终在大盘上面。现在再加上一个条件:不允许直接把盘从1号柱移动到3号柱,也不允许直接把盘从3号柱移动到1号柱。
把盘按半径从小到大用1∽N编号。每种状态用N个整数表示,第i个整数表示i号盘所在的柱的编号,则N=2时的移动方案为:
(1,1)—>(2,1)—>(3,1)—>
(3,2)—>(2,2)—>(1,2)—>
(1,3)—>(2,3)—>(3,3)
初始状态为第0步,编程求在某步数时的状态。

Input

输入文件的第一行为整数(1<=T<=50000),表示输入数据的组数。
接下来的T行,每行有两个整数N,M(1<=N<=19,0<=M<=移动N个圆盘所需的步数)。

Output

输出文件共有T行。
对于每组输入数据,输出N个整数表示移动N个盘在M步时的状态,每两个数之间用一个空格隔开,行首和行末不要有多余的空格。

Sample Input

4
2 0
2 5
3 0
3 1

Sample Output

1 1
1 2
1 1 1
2 1 1

Hint

 

Source