Մուտքում տրված n թվի համար պահանջվում է կառուցել Պասկալի եռանկյուն կազմված n+1 մակարդակներից։ Օրինակ n = 2 դեպքում 

1

1 1

1 2 1

Input

Ոչ բացասական ամբողջ թիվ՝ n ≤ 30:

Output

n+1 հատ տող՝ ամեն տողում Պասկալի եռանկյան համապատասխան մակարդակը։

Example

Input:
3

Output:
1
1 1
1 2 1
1 3 3 1