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
...