TOJ 3072

//组数：卡塔南公式 
//大致题意：输出所有可能出战顺序 
#include<iostream> 
#include<algorithm> 
#include<stack> 
using namespace std; 
bool is_ok(int *a,int n)
{ 
    int i,j,k=0;
    stack<int> s; 
    for(i=1;i<=n;++i) 
    { 
        s.push(i); 
        if(i==a[k]) 
        { //一般把判空放在前面，因为站为空时，s.top()会内存错误 
            while(!s.empty()&&s.top()==a[k]) 
            { 
                s.pop(); 
                ++k; 
            } 
        } 
    } 
    if(s.empty()) 
        return true; 
    return false; 
} 
int main() 
{ 
    int i,j,k,T;
    int a[10];
    int n; 
    cin>>T; 
    while(T--) 
    { 
        cin>>n; 
        for(i=0;i<n;i++)
            a[i] = i+1;                
        do
        { 
            if(is_ok(a,n)) 
            { 
                for(i=0;i<n;++i) 
                    cout<<a[i]; 
                cout<<endl; 
            } 
        }while(next_permutation(a,a+n));
    } 
    return 0; 
}