A young schoolboy would like to calculate the sum ∑n i=1 for some fixed natural k and different natural n. He observed that calculating ik for all i (1 ≤ i ≤ n) and summing up results is a too slow way to do it, because the number of required arithmetical operations increases as n increases. Fortunately, there is another method which takes only a constant number of operations regardless of n. It is possible to show that the sum Sk(n) is equal to some polynomial of degree k + 1 in the variable n with rational coefficients, i.e., () for some integer numbers M, ak+1, ak, . . . , a1, a0. We require that integer M be positive and as small as possible. Under this condition the entire set of such numbers (i.e. M,ak+1,ak,...,a1,a0) will be unique for the given k. You have to write a program to find such set of coefficients to help the schoolboy make his calculations quicker. Input The input file contains several datasets, each of them containing a single integer k (0 ≤ k ≤ 20). The first line of the input contains the number of datasets, and it’s followed by a blank line. There’s also a blank line between datasets. Output For each dataset, write integer numbers M,ak+1,ak,...,a1,a0 to the output file in the given order. Numbers should be separated by one space. Remember that you should write the answer with the smallest positive M possible. Print a blank line between consecutive outputs. Sample input 1 2 Sample Output 62310 Sk(n) = ik Sk(n)= M1 ak+1nk+1 +aknk +...+a1n+a0