Let f(n, k) is the number of length n binary strings for which the length of the longest substring of ones is equal to k. You have to build a table of these values.

Input

None.

Output

63 lines - the n-th of them consists of n+1 values: f(n, 0) f(n, 1) ... f(n, n).

Example

1 1
1 2 1
1 4 2 1
1 7 5 2 1
...