Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1492
Maximum Clique

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex.


Input

Input contains multiple tests. For each test:

The first line has one integer n, the number of vertex. (1 < n <= 50)

The following n lines has n 0 or 1 each, indicating whether an edge exists between i (line number) and j (column number).

A test with n = 0 signals the end of input. This test should not be processed.


Output

One number for each test, the number of vertex in maximum clique.


Sample Input

5
0 1 1 0 1
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
1 1 1 1 0
0


Sample Output

4



Author: CHENG, Long
Source: ZOJ Monthly, February 2003
Submit    Status