"In graph theory, an arborescence is a directed graph in which, for a vertex v called the root and any other vertex u, there is exactly one directed path from v to u. In other words, an arborescence is a directed, rooted tree in which all edges point away from the root. Every arborescence is a directed acyclic graph."

-- from Wikipedia, the free encyclopedia

You are given a directed graph with N vertices, and your task is to count the number of different arborescences of size N that can be found in the given graph.

Two arborescences are considered different when they consist of different edges.

Input

Input consists of multiple test cases.

For each test case, the first line contains one integer N described as above.

N lines follows, each consists of N characters, either '0' or '1', representing the adjacency matrix of the graph.

The directed graph contains edge (i,j) if and only if the jth character of the ith line of the matrix is '1'.

The graph consists of no more than 8 vertices.

End of input is indicated by a line consisting of a single 0.

Output

For each test case, output one line consisting of one single integer, the number of arborescences.

Example

Input:
2
00
00
2
01
10
0
Output:
0
2