Паскалийн гурвалжин бол нэг төрлийн тоонуудын загвар юм. Паскалийн гурвалжин гэдэг нь өмнөх түвшний утгуудыг ашиглан олох боломжтой байдаг.

Өөрөөр хэлбэл \(P[x][y]=P[x-1][y-1]+P[x-1][y]\) хэлбэртэй байдаг.

Таны даалгавар бол паскал-ийг гурвалжинг хэвлэх явдал юм.

Input

Оролтын файлын эхний мөрөнд паскал-ийг гурвалжны хэвлэх мөрийн тоо болох n гэсэн бүхэл тоо өгөгдөнө.

Output

Гаралтын файлд паскал-ийн гурвалжны эхний n мөрийг мөр бүрд хэвлэнэ.

Хязгаарлалт

• \( 0 < n \le 70 \)

Example

Input-1:

3

Output-1:

1
1 1
1 2 1

Input-2:

5

Output-2:

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