Хлопчику Халеку дуже сподобалась алгебра в університеті. Там він дізнався, що нульова матриця розміру ~n \times n~ це таблиця чисел, в якій елементи головної діагоналі рівні одиниці, а всі інші рівні нулю. (Головна діагональ містить елементи, у яких номер стовпця співпадає з номером рядка, тобто ~a_{1,1},a_{2,2},a_{3,3}...~).

Допоможіть Халеку і напишіть програму, яка виводить шукану матрицю розміру ~n \times n~.

Input

В єдиному рядку задано одне ціле число n ~(1\le n\le10^3)~.

Output

Виведіть шукану матрицю.

Sample Input 1

4

Sample Output 1

1 0 0 0 
0 1 0 0 
0 0 1 0 
0 0 0 1

Sample Input 2

7

Sample Output 2

1 0 0 0 0 0 0 
0 1 0 0 0 0 0 
0 0 1 0 0 0 0 
0 0 0 1 0 0 0 
0 0 0 0 1 0 0 
0 0 0 0 0 1 0 
0 0 0 0 0 0 1