Имеется шахматная доска с n * n клетками. Разместите на ней n ферзей таким образом, чтобы ни один ферзь не бил другого.

Входные данные

Размер шахматной доски n (1 ≤ n ≤ 10).

Выходные данные

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