시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

A game designer wants to build a modified chess board of size n by n. At certain squares there will be placed pillars that prevent placement of pieces and also prevent attacks across them.

Before shipping the specifications to a manufacturer, the designer wants to know what is the maximum number of non-attacking queens that can be placed on each of his designs. Recall that queens can attack vertically, horizontally and diagonally as far as possible until the end of board (or, in our case, until a pillar is reached). Also of interest is how many different ways this maximum number can be achieved. 

입력

Input consists of scenarios. Each scenario starts with an integer n (n <= 10). Input ends when n = 0. The next n lines, each containing n characters represent the rows of the chess board. Here, a '0' represents and open square and a '1' represents a pillar. 

출력

For each case output the maximum number queens that can be placed, followed by the number of different ways possible (separated by a single space). 

예제 입력

3
010
111
000
6
000000
000000
000000
000000
000000
000000
6
000010
001110
111011
010110
011010
010010
0

예제 출력

3 3
6 4
7 270

힌트