Description

杨辉三角形又称Pascal三角形，它的第$i+1$行是$(a+b)i$的展开式的系数。 它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。 下面给出了杨辉三角形的前$4$行：
$1$
$1 1$
$1 2 1$
$1 3 3 1$
给出$n$，输出它的前$n$行。

Format

Input

输入包含一个数$n$。$(1 < = n < = 34。)$

Output

输出杨辉三角形的前$n$行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。

Samples

4 

1
1  1
1  2  1
1  3  3  1