题目描述

杨辉三角是一种有规律的数字排列。杨辉三角中的第 $i$ 行有 $i$ 个数，每一行的第一个数和最后一个数都是 $1$，其余的数都等于它上方两个数之和。

请输出杨辉三角的前 $n$ 行。

输入格式

一个整数 $n$，表示行数

输出格式

按样例中的格式输出杨辉三角前 $n$ 行

样例

5

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

数据范围

对于所有测试点，保证 $1≤n≤10$。