http://poj.org/problem?id=1037
//* @author:
import java.util.*;
public class Main{
static final int MAX=21;//���20��ľ��
static long w[][];//w�����еĸ���
static long m[][];//m�����еĸ���m[x][n]Ϊ��n��Ȳ�ͬ��ľ����ɵ�դ8�У������е�x��ľ��ʼ�ġ�M�������еĸ���
private int n;//ľ��ĸ���
private long c;//���
private boolean flag[];
private boolean print;
static {//��ʼ����̬��
w=new long[MAX][MAX];
m=new long[MAX][MAX];
w[1][1] = 1; m[1][1] = 1;
w[1][2] = 0; m[1][2] = 1;
w[2][2] = 1; m[2][2] = 0;
for (int i = 3; i < MAX; i++)
for (int j = 1; j < MAX; j++){
for (int k = 1; k < j; k++)
w[j][i] += m[k][i - 1];
for (int k = j; k < i; k++)
m[j][i] += w[k][i - 1];
}
}
public Main(int n,long c){
this.n=n;
this.c=c;
flag=new boolean[MAX];
print=false;
}
private void fand(int k, int m){
for (int i = 1; i <= m; i++)
if (flag[i] && i <= k){
k++; m++;
}
flag[k] = true;
if (print) System.out.print(" "+k);
else{
System.out.print(k);
print = true;
}
}
private void doIt(){
int k = 1;//��������ǰ���ľ������
print = false;
boolean direct = true, first = true;
while(n!=0){
if (direct)
if (c > w[k][n]){//����Ŵ����Ե�k��ľ��ʼ�ġ�w�������еĸ���˵��������������Щ����֮��
c -= w[k++][n];//���±�ţ�ͬʱ��һ��ľ��
if (first) {direct = false; k--;}//����Dz��ҵ�һ��ľ���Ҫ��"m"������
}else{
fand(k, n--);//�ҵ�k,����ľ�������1
first = false;
direct = false;
k = 1;
}
else
if (c > m[k][n]){//����Ŵ����Ե�k��ľ��ʼ�ġ�m�������еĸ���˵��������������Щ����֮��
c -= m[k++][n];//���±�ţ�ͬʱ��һ��ľ��
if (first) direct = true;//���ҵ�һ��ľ�����
}else{
fand(k, n--);
first = false;
direct = true;
}
}
System.out.println();
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t, n;
long c;
t=sc.nextInt();;
while((t--)!=0){
n=sc.nextInt();
c=sc.nextLong();
Main m=new Main(n,c);
m.doIt();
}
}
}