N Ферзів - розстановка

На шахівниці розміром n * n клітинок потрібно розмістити n ферзів так, щоб жоден з них не загрожував іншому.

Вхідні дані

Розмір шахівниці n (1 ≤ n ≤ 10).

Вихідні дані

Якщо можливо розмістити всіх n ферзів так, щоб жоден не загрожував іншому, виведіть n рядків, кожен з яких містить n цілих чисел. Число в i-му рядку та j-му стовпці дорівнює 1, якщо ферзь розташований у клітинці (i, j), і 0 в іншому випадку. Якщо існує кілька можливих розташувань ферзів, виведіть будь-яке з них. Якщо розмістити всіх n ферзів бажаним чином неможливо, виведіть "Not possible" (без лапок).

Приклади