Invariant Board States on an n×n Chessboard

Consider an \(n\times n\) chessboard in which each cell is filled with either \(1\) or \(-1\). A transformation is defined so that every cell is replaced by the product of the numbers in its (up to) four adjacent neighbors (up, down, left, right). For border cells, only the existing neighbors are used; by convention the product of an empty set is defined to be \(1\).

A board configuration is said to be an invariant state if after the transformation the board remains unchanged, i.e. if for every cell \(a_{i,j}\) the following condition holds:

[ a_{i,j} = \prod_{(p,q)\in N(i,j)} a_{p,q}, ]

where \(N(i,j)\) denotes the set of valid neighbors of cell \((i,j)\). Note that some configurations, such as the board with every cell equal to \(1\), are invariant. Two invariant states are considered essentially equivalent if one can be transformed to the other by a rotation or reflection (i.e. if they belong to the same symmetry class under the dihedral group \(D_4\)).

Your task is to find all essentially different invariant states of the board.

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 4\)).

outputFormat

First, output an integer representing the number of essentially different invariant states. Then, for each invariant state, output the board as \(n\) lines with \(n\) space-separated integers per line. Print a blank line after each board. The order of the boards is arbitrary as long as no two boards are essentially equivalent (i.e. if one can be obtained from another by rotation or reflection).

sample

1

1
1