Queen Kingdom

A game designer wants to build a modified $n \times n$ chessboard. On some squares stand pillars: a pillar blocks a piece from being placed on that square, and it also blocks any attack from passing through it.

Before sending the design to a manufacturer, the designer wants to know, for each board layout, the maximum number of queens that can be placed so that no two attack each other. As on a normal chessboard, a queen attacks along its row, its column, and both diagonals, extending outward until it reaches the edge of the board — but on this board an attack also stops the moment it reaches a pillar. The designer also wants to know how many distinct placements achieve that maximum.

The input contains several scenarios. Each scenario begins with a line holding a single integer $n$ ($1 \le n \le 10$). The input ends with a line containing $0$, which is not processed.

The next $n$ lines each contain $n$ characters describing the rows of the board. A 0 is an open square and a 1 is a pillar.

For each scenario, print one line with two integers separated by a single space: the maximum number of queens that can be placed so that no two attack each other, followed by the number of distinct placements that achieve this maximum.