#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
long long C[25][25] = {};
long long M[25] = {}, A[25][25] = {};
long long llabs(long long v) {
    return v < 0 ? -v : v;
}
void init() {
    C[0][0] = 1;
    for(int i = 1; i < 25; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++)
            C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
    // sum of powers
    M[0] = 1, A[0][1] = 1; // sigma(k^0) = n
    for(int i = 1; i <= 20; i++)  {
        M[i] = i + 1;
        long long val = 1;
        for(int j = 0; j <= i - 1; j++)
            val = val / __gcd(val, M[j]) * M[j];
        M[i] *= val;
//		printf("%lld %lld\n", M[i], val);
        for(int j = 0; j <= i - 1; j++)
            for(int k = 0; k <= j + 1; k++)
                A[i][k] -= A[j][k] * val / M[j] * C[i + 1][j];
        for(int j = 0; j <= i + 1; j++)
            A[i][j] += val * C[i+1][j];
        A[i][0] -= val * 1;
        long long g = M[i];
        for(int j = 0; j <= i + 1; j++)
            g = __gcd(g, llabs(A[i][j]));
        M[i] /= g;
        for(int j = 0; j <= i + 1; j++)
            A[i][j] /= g;
    }
}
/*
find sigma(i^2)
(i + 1)^3 - (i)^2 = 3*(i)^2 + 3i + 1
=> i^2 = 1/3 * ((i + 1)^3 - (i)^2 - 3i - 1)
=> sigma(i^2) = sigma(1/3 * ((i + 1)^3 - (i)^2 - 3i - 1))
=>            = 1/3 (sigma((i + 1)^3 - (i)^2) + sigma(-3i - 1)) 
=> // sigma((i + 1)^3 - (i)^3) = (n + 1)^3 - 1
=>            = 1/3 ((n + 1)^3 - 1 + sigma(-3i - 1)) 
... so
 */
int main() {
    init();
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        printf("%lld", M[n]);
        for(int i = n + 1; i >= 0; i--)
            printf(" %lld", A[n][i]);
        puts("");
        if(testcase)
            puts("");
    }
    return 0;
}

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 65536
#define INF 0x3f3f3f3f
long long sum[MAXN], ssum[MAXN], isum[MAXN], issum[MAXN];
// binary indexed tree
int BIT[MAXN<<1];
int query(int x) {
    int ret = 0;
    while(x) {
        ret = max(ret, BIT[x]);
        x -= x&(-x);
    }
    return ret;
}
void modify(int x, int v, int L) {
    while(x <= L) {
        BIT[x] = max(BIT[x], v);
        x += x&(-x);
    }
}
int query2(int x) {
    int ret = INF;
    while(x) {
        ret = min(ret, BIT[x]);
        x -= x&(-x);
    }
    return ret;
}
void modify2(int x, int v, int L) {
    while(x <= L) {
        BIT[x] = min(BIT[x], v);
        x += x&(-x);
    }
}
int cases = 0, preA[MAXN], sufA[MAXN], start[MAXN], cover[MAXN<<1];
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    int testcase, n, A[MAXN];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &A[i]), start[i] = 0, cover[A[i] + MAXN] = -1;
        
        int L = 50000 + MAXN;
        for(int i = 0; i <= L; i++)
            BIT[i] = 0;
        for(int i = 1; i <= n; i++) {
            preA[i] = query(A[i] + MAXN);
            modify(A[i]+MAXN, i, L);
            if(preA[i] <= cover[A[i] + MAXN])
                start[i] = cover[A[i] + MAXN] + 1;
            cover[A[i] + MAXN] = i;
        }
        for(int i = 0; i <= L; i++)
            BIT[i] = n + 1;
        for(int i = n; i >= 1; i--) {
            sufA[i] = query2(A[i] + MAXN);
            modify2(A[i]+MAXN+1, i, L);
        }
        
        for(int i = 1; i <= n; i++)
            sum[i] = sum[i-1] + A[i];
        for(int i = 1; i <= n; i++)
            ssum[i] = ssum[i-1] + sum[i];
            
        isum[n+1] = issum[n+1] = 0;
        for(int i = n; i >= 1; i--)
            isum[i] = isum[i+1] + A[i];
        for(int i = n; i >= 1; i--)
            issum[i] = issum[i+1] + isum[i];
        
        long long ret = 0;
        for(int i = 1; i <= n; i++) {
            long long suma, a, sumb, b;
            if(start[i]) {
                suma = issum[start[i]] - issum[i], a = i - start[i];
                sumb = ssum[sufA[i]-1] - ssum[i], b = sufA[i] - i - 1;
                suma -= isum[i] * a;
                sumb -= sum[i] * b;
            } else {
                suma = issum[preA[i]+1] - issum[i], a = i - preA[i] - 1;
                sumb = ssum[sufA[i]-1] - ssum[i], b = sufA[i] - i - 1;
                suma -= isum[i] * a;
                sumb -= sum[i] * b;
            }
//			printf("index %d\n", i);
//			printf("%lld %lld\n", ssum[sufA[i]-1], ssum[i]);
//			printf("%lld %lld %lld %lld -- %lld\n", suma, a, sumb, b, (suma - A[i]*a*(a+1)/2) * (b + 1) + (sumb - A[i]*b*(b+1)/2) * (a + 1));
            ret += (suma - A[i]*a*(a+1)/2) * (b + 1) + (sumb - A[i]*b*(b+1)/2) * (a + 1);
//			long long test = 0;
//			for(int j = i; j >= 1; j--) {
//				if(A[j] < A[i])
//					break;
//				for(int k = i; k <= n; k++) {
//					if(A[k] < A[i])	break;
//					for(int l = j; l <= k; l++)
//						test += A[l] - A[i];
//				}
//			}
//			printf("DEBUG %lld\n", test);
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
1
5
1 2 3 4 5
10
10
-7 2 -6 7 -9 5 -5 -3 9 3 
10
1 -7 9 2 4 7 -10 8 0 0 
10
-8 9 4 -8 1 2 -3 2 8 8 
10
-3 -4 0 -2 5 9 -3 -4 2 1 
10
3 -8 -9 -4 8 -9 -7 6 -10 -9 
10
-7 0 -2 8 -6 6 9 -5 -1 -3 
10
1 -10 7 -1 7 -10 5 -1 -10 9 
10
-2 9 -8 8 -7 0 -1 -8 7 -9 
10
-9 2 3 -8 -10 9 7 9 1 3 
10
3 5 1 -4 -6 -3 0 2 -5 -5 
*/

#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
int getSuit(char c) {
    switch(c) {
        case 'C': return 0;
        case 'D': return 1;
        case 'H': return 2;
        case 'S': return 3;
    }
}
int getRank(char c) {
    switch(c) {
        case '0' ... '9': return c - '0';
        case 'A': return 1;
        case 'X': return 10;
        case 'J': return 11;
        case 'Q': return 12;
        case 'K': return 13;
    } 
}
bool suitCmp(pair<int, int> x, pair<int, int> y) {
    if(x.first != y.first)
        return x.first < y.first;
    return x.second < y.second;
}
bool rankCmp(pair<int, int> x, pair<int, int> y) {
    if(x.second != y.second)
        return x.second < y.second;
    return x.first < y.first;
}
int getType(vector< pair<int, int> > cards) {
    vector< pair<int, int> >::iterator it;
    
    sort(cards.begin(), cards.end(), suitCmp);
    if(cards[0].first == cards[4].first) { // all same suit
        for(int i = 0; i < 13; i++) {
            int ok = 1;
            for(int j = 0; j < 5; j++) {
                int r = (i + j)%13 + 1;
                it = find(cards.begin(), cards.end(), make_pair(cards[0].first, r));
                ok &= it != cards.end();
            }
            if(ok)
                return 9;
        }
    }
    
    sort(cards.begin(), cards.end(), rankCmp);
    if(cards[0].second == cards[3].second ||
        cards[1].second == cards[4].second)
            return 8;
            
    sort(cards.begin(), cards.end(), rankCmp);
    if(cards[0].second == cards[2].second &&
        cards[3].second == cards[4].second)
            return 7;
    if(cards[0].second == cards[1].second &&
        cards[2].second == cards[4].second)
            return 7;
            
    sort(cards.begin(), cards.end(), suitCmp);
    if(cards[0].first == cards[4].first)
        return 6;
        
    sort(cards.begin(), cards.end(), suitCmp);
    for(int i = 0; i < 13; i++) {
        int ok = 1;
        for(int j = 0; j < 5; j++) {
            int r = (i + j)%13 + 1;
            for(int k = 0; k < 4; k++) {
                it = find(cards.begin(), cards.end(), make_pair(k, r));
                if(it != cards.end())
                    break;
            }
            ok &= it != cards.end();
        }
        if(ok)
            return 5;
    }
    
    sort(cards.begin(), cards.end(), rankCmp);
    if(cards[0].second == cards[2].second ||
        cards[1].second == cards[3].second ||
         cards[2].second == cards[4].second)
            return 4;
    
    sort(cards.begin(), cards.end(), rankCmp);
    if(cards[0].second == cards[1].second &&
        cards[2].second == cards[3].second)
            return 3;
    if(cards[0].second == cards[1].second &&
        cards[3].second == cards[4].second)
            return 3;
    if(cards[1].second == cards[2].second &&
        cards[3].second == cards[4].second)
            return 3;
            
    sort(cards.begin(), cards.end(), rankCmp);
    for(int i = 1; i < 5; i++)
        if(cards[i].second == cards[i-1].second)
            return 2;
    return 1;
}
int main() {
    int testcase;
    char grid[5][5][5];
    scanf("%d", &testcase);
    while(testcase--) {
        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                scanf("%s", grid[i][j]);
        int cnt[10] = {};
        for(int i = 0; i < 5; i++) {
            vector< pair<int, int> > cc;
            for(int j = 0; j < 5; j++)
                cc.push_back(make_pair(getSuit(grid[i][j][1]), getRank(grid[i][j][0])));
            int f = getType(cc);
            cnt[f]++;
        }
        
        for(int i = 0; i < 5; i++) {
            vector< pair<int, int> > cc;
            for(int j = 0; j < 5; j++)
                cc.push_back(make_pair(getSuit(grid[j][i][1]), getRank(grid[j][i][0])));
            int f = getType(cc);
            cnt[f]++;
        }
        
        for(int i = 1; i <= 9; i++) {
            if(i > 1)	printf(", ");
            printf("%d", cnt[i]);
        }
        puts("");
        if(testcase)
            puts("");
    }
    return 0;
}
/*
2
AS 2S 3S 4S 5S
AC 2H 3H 5C 4C
AH 2D KC KH 5D
AD 3D KD 9D 8D
XH 3C XC XS 8C
AS 2S 3S 4S 6S
AC 2H 3H 5C 4C
AH 2D KC KH 5D
AD 3D KD 9D 8D
XH 3C XC XS 8C
*/

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
#define MAXN 5024288
#define INF 0x3f3f3f3f
long long A[MAXN], SM[MAXN], SB[MAXN];
// binary index tree
int BIT[MAXN<<1];
void modify(int x, int v, int L) {
    while(x <= L) {
        BIT[x] = max(BIT[x], v);
        x += x&(-x);
    }
}
int query(int x) {
    int ret = - INF;
    while(x) {
        ret = max(ret, BIT[x]);
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int testcase, N, X;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &N, &X);
        for(int i = 1; i <= N; i++)
            scanf("%lld", A+i);
        
        for(int i = 1; i <= N; i++)
            SM[i] = SM[i-1] + A[i];
        for(int i = 0; i <= N; i++)
            SB[i] = SM[i];
        for(int i = 1; i <= N + 1; i++)
            BIT[i] = - INF;
        sort(SB, SB + N + 1);
        int M = unique(SB, SB + N + 1) - SB;		
        int ret = INF;
        for(int i = 0; i <= N; i++) {
            long long v = SM[i] - X;
            int pos = upper_bound(SB, SB + M, v) - SB;
            if(pos - 1 >= 0 && i)  {
                ret = min(ret, i - query(pos));
//				printf("query %d\n", i - query(pos));
            }
            pos = upper_bound(SB, SB + M, SM[i]) - SB;
            modify(pos, i, M);
//			printf("%lld %d\n", v, pos);
        }
        
        printf("%d\n", ret == INF ? -1 : ret);
    }
    return 0;
}
/*
3
5 4
1 2 1 2 1
6 -2
-5 -6 -7 -8 -9 -10
5 3
-1 1 1 1 -1
*/

#include <stdio.h>
#include <sstream>
#include <iostream>
#include <math.h>
using namespace std;
const double pi = acos(-1);
double A, B, C, N;
char* getLot() {
    char line[1024], *v;
    string ret = "", token;
    int tokenCnt = 0;
    while(tokenCnt%4 != 1) {
        while((v = gets(line)) && line[0] != '\0') {
            ret += " ", ret += line;
            stringstream ss(line);
            while(ss >> token)
                tokenCnt++;
        }
        if(!v)
            return v;
    }
    stringstream sin(ret);
    double lotsize, baseline, ridgeline, dist, theta;
    double a = 0, b = 0;
    sin >> lotsize;
    while(sin >> baseline >> ridgeline >> dist >> theta) {
        a += (baseline + ridgeline) * dist/2.0;
        b += (baseline + ridgeline) * dist/2.0 * cos(theta / 180.0 * pi);	
    }
    printf("%9.2lf     %10.2lf     %8.2lf%%\n", a, b, b * 100 /lotsize);
    A += a, B += b, C += lotsize, N++;
    return v;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout);
    
    puts("Roof Area     Floor Area     % Covered");
    puts("---------     ----------     ---------");
    char line[1024];
    while(true) {
        if(getLot()) {
        } else {
            break;
        }
    }
    puts("");
    printf("Total surface area of roofs  %10.2lf\n", A);
    printf("Total area covered by roofs  %10.2lf\n", B);
    printf("Percentage of total area covered by roofs  %6.2lf%%\n", B*100/C);
    printf("Average roof surface area per lot      %10.2lf\n", A/N);
    printf("Average floor space covered per lot    %10.2lf\n", B/N);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct SuffixArray {
    int sa[1005], h[1005], n;
    int w[1005], ta[1005], tb[1005];
    char str[1005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
int main() {
    SuffixArray in;
    while(gets(in.str) && in.str[0] != '\0') {
    	int n = 0;
    	for(int i = 0; in.str[i]; i++)
    		if(in.str[i] != ' ')
    			in.str[n++] = in.str[i];
    	in.str[n] = '\0';
    	
        in.build();
        in.build_h();
        
        if(n == 0)
        	puts("0");
        for(int i = 1; i <= in.n; i++) {
        	int cnt = 0, ret = 0;
        	for(int j = 0; j < in.n; j++) {
        		if(in.h[j] >= i)
        			cnt++;
        		else
        			ret = max(ret, cnt), cnt = 0;
        	}
        	ret = max(ret, cnt);
        	if(ret <= 0)
        		break;
        	printf("%d\n", ret + 1);
        }
        puts("");
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int n, m, cases = 0, x;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        int bad[1024] = {}, A[1024][16];
        int badCount = 0;
        for(int i = 0; i < m; i++) {
            int mark[16] = {};
            for(int j = 0; j < n; j++) {
                scanf("%d", &x);
                A[i][j] = x;
                if(x > n || x < 1) {
                    bad[i] = 1;
                    continue;
                }
                mark[x]++;
                if(mark[x] > 1)
                    bad[i] = 1;
            }
            badCount += bad[i];
        }
        
        printf("Election #%d\n", ++cases);
        printf("   %d bad ballot(s)\n", badCount);
        
        int Atop[1024] = {}, alive[1024] = {}, aliveCount = n;
        for(int i = 1; i < n; i++) {
            int votes[16] = {}, mx = 0, del = -1;
            for(int j = 0; j < m; j++) {
                if(bad[j])	continue;
                while(alive[A[j][Atop[j]]])
                    Atop[j]++;
                votes[A[j][Atop[j]]]++;
            }
            for(int j = 1; j <= n; j++)
                mx = max(mx, votes[j]);
            for(int j = 1; j <= n; j++) {
                if(votes[j] < mx && alive[j] == 0)
                    del = j, mx = votes[j];
            }
            if(del == -1)	break;
            alive[del] = 1, aliveCount--;
        }
        if(aliveCount == 1) {
            for(int i = 1; i <= n; i++)
                if(alive[i] == 0)
                    printf("   Candidate %d is elected.\n", i);
        } else {
            printf("   The following candidates are tied:");
            for(int i = 1; i <= n; i++)
                if(alive[i] == 0)
                    printf(" %d", i);
            puts("");
        }
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
struct edge {
    int to, label;
    edge(int a=0, int b=0):
        to(a), label(b) {}
    bool operator<(const edge &x) const {
        return label < x.label;
    }
};
#define MAXN 2048
vector<edge> g[MAXN];
int label_used[MAXN];
deque<int>	path;
void dfs(int u) {
    for(int i = 0; i < g[u].size(); i++) {
        if(label_used[g[u][i].label] == 0) {
        	label_used[g[u][i].label] = 1;
            dfs(g[u][i].to);
            path.push_front(g[u][i].label);
        }
    }
}
int main() {
    int x, y, z;
    while(true) {
    	for(int i = 0; i < MAXN; i++)
    		g[i].clear();
    	int e = 0, start = 0;
    	while(scanf("%d %d", &x, &y) == 2) {
    		if(x == 0 && y == 0)
    			break;
    		/* Johnny lives at the junction ending the 1st street 
				input with smaller number. */
    		if(e == 0)
    			start = min(x, y);
    		scanf("%d", &z);
    		g[x].push_back(edge(y, z));
    		g[y].push_back(edge(x, z));
    		e++;
    	}
    	if(e == 0)	break;
    	
    	int odd = 1;
    	for(int i = 0; i < MAXN; i++) {
    		odd &= g[i].size()%2 == 0;
    	}
    	if(!odd) {
    		puts("Round trip does not exist.\n");
    		continue;
    	}
    	for(int i = 0; i < MAXN; i++)
    		sort(g[i].begin(), g[i].end());
    	memset(label_used, 0, sizeof(label_used));
    	path.clear();
    	dfs(start);
    	for(int i = 0; i < path.size(); i++) 
    		printf("%d%c", path[i], i == path.size()-1 ? '\n' : ' ');
    	puts("");
    }
    return 0;
}

#include <stdio.h>
#include <algorithm>
using namespace std;
int notes[128] = {};
int kmpTable[500005];
void KMPtable(int *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(int T[], int P[], int tlen, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1) {
            j = kmpTable[j];
            return i;
        }
    }
    return -1;
}
int main() {
    int M, T;
    int A[100005], B[10005];
    char s[10];
    notes['C'] = 0, notes['D'] = 2;
    notes['E'] = 4,	notes['F'] = 5;
    notes['G'] = 7,	notes['A'] = 9;
    notes['B'] = 11;
    while(scanf("%d %d", &M, &T) == 2 && M + T) {
        int prev, x;
        for(int i = 0; i < M; i++) {
            scanf("%s", &s);
            x = (notes[s[0]] + (s[1] == '#') - (s[1] == 'b') + 12)%12;
            if(i)	A[i - 1] = (prev - x + 12)%12;
            prev = x;
        }
        for(int i = 0; i < T; i++) {
            scanf("%s", &s);
            x = (notes[s[0]] + (s[1] == '#') - (s[1] == 'b') + 12)%12;
            if(i)	B[i - 1] = (prev - x + 12)%12;
            prev = x;
        }
        KMPtable(A, M - 1);
        puts( KMPmatching(A, B, M - 1, T - 1) >= 0 ? "S" : "N");
    }
    return 0;
}